Large-precision homomorphic comparison using bootstrapping
Systems and methods for improving homomorphic encryption are provided. A processor receives an encrypted ciphertext; splits the encrypted ciphertext into a plurality of smaller digits; applies a homomorphic floor function to clear a least significant bit from a current smaller digit; scales down the encrypted ciphertext, using modulus switching, thereby changing the ciphertext modulus to a new modulus; applies a bootstrapping procedure for a sign evaluation function to determine a sign of the scaled down encrypted ciphertext; and transmits the sign with the ciphertext to a server for subsequent use.
1. A computer implemented method for improving homomorphic encryption, the method comprising:
receiving, at a computer processor, a homomorphically encrypted ciphertext;
splitting, by the computer processor, the homomorphically encrypted ciphertext into a plurality of smaller digits;
for each smaller digit of the plurality of smaller digits:
(i) applying, by the computer processor, a homomorphic floor function to clear a digit of the plurality of smaller digits which corresponds to a least significant bit of the homomorphically encrypted ciphertext;
(ii) reconstructing, by the computer processor, the homomorphically encrypted ciphertext without the digit of the plurality of smaller digits cleared at (i), and scaling down the reconstructed homomorphically encrypted ciphertext using modulus switching, thereby changing the ciphertext modulus to a new modulus;
iteratively repeating steps (i) and (ii) until the new modulus is less than or equal to the modulus of the smaller digit under consideration;
applying, by the processor, a bootstrapping procedure for a sign evaluation function to determine a sign of the scaled down homomorphically encrypted ciphertext;
transmitting, by the computer processor, the sign with the homomorphically encrypted ciphertext to a server; and
comparing the homomorphically encrypted ciphertext to another homomorphically encrypted ciphertext by evaluating a difference between the two homomorphically encrypted ciphertexts, and determining a sign of the difference.
2. The method of claim 1 , wherein the homomorphic floor function is a negacyclic function.
3. The method of claim 1 , wherein applying the homomorphic floor function comprises using a function ƒ 0 (x), given by
f
0
(
x
)
=
{
-
q
/
4
,
if
0
≤
x
<
q
/
2
q
/
4
,
otherwise
.
4. The method of claim 1 , wherein applying the homomorphic floor function comprises using a function ƒ 1 (x), given by
f
1
(
x
)
=
{
x
,
if
x
<
q
/
2
q
/
2
-
x
,
otherwise
.
5. The method of claim 1 , wherein applying the homomorphic floor function comprises using a function ƒ 2 (x), given by
f
2
(
x
)
=
{
-
q
/
4
,
if
0
≤
x
<
q
/
2
q
/
4
,
if
q
/
2
≤
x
<
3
q
/
4
0
,
otherwise
.
6. The method of claim 1 , wherein the step of applying the homomorphic floor function is implemented by an arbitrary function evaluation using a lookup table for small plaintext moduli which support FHEW bootstrapping.
7. The method of claim 1 , wherein the subsequent use comprises applying the transmitted sign and ciphertext to a machine learning decision tree action or neural network inference.
8. The method of claim 1 , wherein the encrypted ciphertext corresponds to an integer modulo Q/α, and wherein a noise e of the encrypted ciphertext is constrained such that |e|<β, wherein β≤α/4.
9. A system for improving homomorphic encryption, the system comprising at least one processor and a memory containing instructions which, when executed by the at least one processor, cause the at least one processor to:
receive a homomorphically encrypted ciphertext;
split the homomorphically encrypted ciphertext into a plurality of smaller digits;
for each smaller digit of the plurality of smaller digits:
(i) apply a homomorphic floor function to clear a digit of the plurality of smaller digits which corresponds to a least significant bit of the homomorphically encrypted ciphertext;
(ii) reconstruct the homomorphically encrypted ciphertext without the digit of the plurality of smaller digits cleared at (i), and scale down the reconstructed homomorphically encrypted ciphertext, using modulus switching, thereby changing the ciphertext modulus to a new modulus;
iteratively repeat steps (i) and (ii) until the new modulus is less than or equal to the modulus of the smaller digit under consideration;
apply a bootstrapping procedure for a sign evaluation function to determine a sign of the scaled down homomorphically encrypted ciphertext;
transmit the sign with the homomorphically encrypted ciphertext to a server; and
compare the homomorphically encrypted ciphertext to another homomorphically encrypted ciphertext by evaluating a difference between the two homomorphically encrypted ciphertexts, and determining a sign of the difference.
10. The system of claim 9 , wherein the homomorphic floor function is a negacyclic function.
11. The system of claim 1 wherein applying the homomorphic floor function comprises using a function ƒ 0 (x), given by
f
0
(
x
)
=
{
-
q
/
4
,
if
0
≤
x
<
q
/
2
q
/
4
,
otherwise
.
12. The system of claim 9 , wherein applying the homomorphic floor function comprises using a function ƒ 1 (x), given by
f
1
(
x
)
=
{
x
,
if
x
<
q
/
2
q
/
2
-
x
,
otherwise
.
13. The system of claim 9 , wherein applying the homomorphic floor function comprises using a function ƒ 2 (x), given by
f
2
(
x
)
=
{
-
q
/
4
,
if
0
≤
x
<
q
/
2
q
/
4
,
if
q
/
2
≤
x
<
3
q
/
4
0
,
otherwise
.
14. The system of claim 9 , wherein the step of applying the homomorphic floor function is implemented by an arbitrary function evaluation using a lookup table for small plaintext moduli which support FHEW bootstrapping.
15. The system of claim 9 , wherein the subsequent use comprises applying the transmitted sign and ciphertext to a machine learning decision tree action or neural network inference.
16. The system of claim 9 , wherein the encrypted ciphertext corresponds to an integer modulo Q/α, and wherein a noise e of the encrypted ciphertext is constrained such that |e|<β, wherein β≤α/4.
17. The system of claim 9 , wherein the at least one processor belongs to the server.
18. A computer program product containing a non-transitory computer readable storage medium storing instructions which, when loaded into a computing device comprising at least one processor cause the at least one processor to:
receive a homomorphically encrypted ciphertext;
split the homomorphically encrypted ciphertext into a plurality of smaller digits;
for each smaller digit of the plurality of smaller digits:
(i) apply a homomorphic floor function to clear a digit of the plurality of smaller digits which corresponds to a least significant bit of the homomorphically encrypted ciphertext;
(ii) reconstruct the homomorphically encrypted ciphertext without the digit of the plurality of smaller digits cleared at (i), and scale down the reconstructed homomorphically encrypted ciphertext, using modulus switching, thereby changing the ciphertext modulus to a new modulus;
iteratively repeat steps (i) and (ii) until the new modulus is less than or equal to the modulus of the smaller digit under consideration;
apply a bootstrapping procedure for a sign evaluation function to determine a sign of the scaled down homomorphically encrypted ciphertext; and
transmit the sign with the homomorphically encrypted ciphertext to a server; and
compare the homomorphically encrypted ciphertext to another homomorphically encrypted ciphertext by evaluating a difference between the two homomorphically encrypted ciphertexts, and determining a sign of the difference.