Performing efficient comparison operations on encrypted data
In computer-implemented technology for comparing first and second values that are encrypted according to a fully homomorphic encryption scheme, the following function is computed: f ( ɛ ( x ) , ɛ ( y ) ) = { ɛ ( 0 ) … if … x ≠ y ɛ ( 1 ) … if … x = y } where ε(.) is a fully homomorphic encryption scheme.
1. A computer-implemented method for comparing a first value and a second value via a fully homomorphic encryption scheme, comprising:
receiving first and second values by an encrypter and encrypting at least one of the first and second values to obtain ε(a i ) and ε(b i ) for each of i=1, . . . , n;
receiving ε(a i ) and ε(b i ) by a homomorphic computer and computing results for a first function ƒ(ε(a i ) and ε(b i ) for each of i=1, . . . , n;
receiving the computed results for each of i=1, . . . , n by a homomorphic product computer and homomorphically computing a product of the results for each of i=1, . . . , n according to the formula
Product
=
∏
i
=
1
n
f
(
ɛ
(
a
i
)
,
ɛ
(
b
i
)
)
and outputting the product, where the product yields
{
ɛ
(
0
)
…
if
…
a
≠
b
ɛ
(
1
)
…
if
…
a
=
b
}
,
where ε(.) is a fully homomorphic encryption scheme, and
where computing the first function and the product reduces computational resources required to compare the first and second values.
2. The computer-implemented method of claim 1 , wherein: said first and said second values received by the encrypter are binary values; and
said first function is computed by
ƒ(ε( a i ),ε( b i ))=(ε( a i )−ε( b i ))·(ε( b i )−ε( a i ))+ε(1) for each of i= 1, . . . , n.
3. The computer-implemented method of claim 2 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.
4. The computer-implemented method of claim 1 , wherein:
said first value is a first binary bit string a 1 a 2 . . . a n represented as a i and encoded into an element of an integer polynomial ring representation to obtain ε(a i ) for i=1, . . . , n and said second value is a second binary bit string b 1 b 2 . . . b n , represented as b i encoded into an element of an integer polynomial ring representation to obtain ε(a i ) for i=1, . . . , n and encrypted to obtain ε(b i ); and
said first function is computed by
ƒ(ε( a i ), b i )=(ε( a i ) b i +ε( a i ) b i )×(−1)+ε(1), where ε( a i )×(−1)+ε(1), and b i = b i ×(−1)+1.
5. The computer-implemented method of claim 4 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.
6. The computer-implemented method of claim 1 , wherein said first and said second values received by the encrypter are non-binary values; and
said first function is computed by
ƒ(ε( a i ),ε( b i ))=ε(1)−[ε( a i )−ε( b i )] p-1 mod p.
7. The computer-implemented method of claim 6 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.
8. A homomorphic comparator for comparing a first value and a second value according to a fully homomorphic encryption scheme, the homomorphic comparator comprising:
an encrypter that receives first and second values by an encrypter and encrypts at least one of the first and second values to obtain ε(a i ) and ε(b i ) for i=1, . . . , n;
a homomorphic computer that receives for computing the function ε(a i ) and ε(b i ) and computes results for a first function ƒ(ε(a i ) and ε(b i ) for each of i=1, . . . , n;
a homomorphic computer that receives the computed results for each of i=1, . . . , n and homomorphically computes a product of the results for each of i=1, . . . , n according to the formula
Product
=
∏
i
=
1
n
f
(
ɛ
(
a
i
)
,
ɛ
(
b
i
)
)
and outputs the product, where the product yields
{
ɛ
(
0
)
…
if
…
a
≠
b
ɛ
(
1
)
…
if
…
a
=
b
}
,
where ε(.) is a fully homomorphic encryption scheme, and
where computing the first function and the product reduces computational resources required to compare the first and second values.
9. The system of claim 8 , wherein:
said first and said second values received by the encrypter are binary values; and
said homomorphic computer computes the first function by computing
ƒ(ε( a i ),ε( b i ))=(ε( a i )−ε( b i ))·(ε( b i )−ε( a i ))+ε(1) for each of i= 1, . . . , n.
10. The system of claim 9 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.
11. The system of claim 8 , wherein:
said first value is a first binary bit string a 1 a 2 . . . a n represented as a i and encoded into an element of an integer polynomial ring representation so as to obtain ε(a i ) for i=1, . . . , n and said second value is a second binary bit string b 1 b 2 . . . b n , represented as b i , encoded into an element of an integer polynomial ring representation so as to obtain ε(a i ) for i=1, . . . , n and encrypted to obtain ε(b i ); and
said homomorphic computer computes the first function
ƒ(ε( a ), b )=( ā ) b +ε( a ) b ))×(−1)+ε(1), where ε( ā )=ε( a )×ε(−1)+ε(1), and b =b ×(−1)+1.
12. The system of claim 11 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.
13. The system of claim 8 , wherein said first and said second values received by the encrypter are non-binary values; and
said homomorphic computer computes the first function by computing
ƒ(ε( a ),ε( b ))=ε(1)−[ε( a )−ε( b )] p-1 mod p.
14. The system of claim 13 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.
15. A computer program product for comparing a first value and a second value according to a fully homomorphic encryption scheme, the computer program product comprising:
a computer readable storage medium having program instructions embodied therewith, the program instructions executable by a computer to cause the computer to:
receive first and second values by an encrypter and encrypt the first and second values to obtain ε(a i ) and ε(b i ) for i=1, . . . , n;
receive ε(a i ) and ε(b i ) by a homomorphic computer and compute results for a first function ƒ(ε(a i ) and ε(b i ) for each of i=1, . . . , n;
receive the computed results for each of i=1, . . . , n by a homomorphic product computer and homomorphically compute a product of the results for each of i=1, . . . , n according to the formula
Product
=
∏
i
=
1
n
f
(
ɛ
(
a
i
)
,
ɛ
(
b
i
)
)
and output the product, where the product yields
{
ɛ
(
0
)
…
if
…
a
≠
b
ɛ
(
1
)
…
if
…
a
=
b
}
,
where ε(.) is a fully homomorphic encryption scheme, and
where computing the first function and the product reduces computational resources required to compare the first and second values.
16. The computer program product of claim 15 , wherein:
said first and said second values received by a the encrypter are binary values; and
said first function is computed by
ƒ(ε( a i ),ε( b i ))=(ε( a i )−ε( b i ))·(ε( b i )−ε( a i ))+ε(1) for each of i= 1, . . . , n.
17. The computer program product of claim 16 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.
18. The computer program product of claim 15 , wherein:
said first value is a first binary bit string a 1 a 2 . . . a n represented as a i and encoded into an element of an integer polynomial ring representation so as to obtain ε(a i ) for i=1, . . . , n and said second value is a second binary bit string b 1 b 2 . . . b n , represented as b i , encoded into an element of an integer polynomial ring representation to obtain ε(a i ) for i=1, . . . , n and encrypted to obtain ε(b i ); and
said first function is computed by
ƒ(ε( a i ), b i )=(ε( a i ) b i +ε( a i ) b i )×(−1)+ε(1), where ε( ā )=ε( a )×(−1)+ε(1), and b =b ×(−1)1.
19. The computer program product of claim 18 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.
20. The computer program product of claim 15 , wherein said first and said second values received by the encrypter are non-binary values; and
said first function is computed by
ƒ(ε( a ),ε( b ))=ε(1)−[ε( a )−ε( b )] p-1 mod p.
21. The computer program product of claim 20 , wherein said first value and said second value comprise a plurality of slots, each slot containing a single ciphertext.