Homomorphic evaluation including key switching, modulus switching, and dynamic noise management
First Claim
1. A computer-implemented method, comprising:
- performing at a computer system homomorphic evaluation of a function on one or more input ciphertexts, where the one or more input ciphertexts were encrypted using a public key of an encryption scheme that also comprises a plurality of secret keys and a plurality of moduli, where the moduli are integers, where the function comprises one or more homomorphic operations, and where performing the homomorphic evaluation comprises performing each of the one or more homomorphic operations for the function, and where performing each of the one or more homomorphic operations comprises;
selecting one or more ciphertexts and determining an estimate of noise in the selected one or more ciphertexts;
for each one of the selected one or more ciphertexts, in response to a determination the noise magnitude meets at least one criterion, performing a modulus switching operation on the ciphertext to convert the ciphertext from one of the plurality of secret keys and a first modulus into a second ciphertext with respect to a same secret key but a second modulus, and updating the noise estimate following the modulus switching operation;
performing the homomorphic operation for the function on the selected one or more ciphertexts;
computing the noise estimate for the result of the homomorphic operation from the noise estimate of the selected one or more ciphertexts;
determining based on the noise estimate whether to perform a modulus switching operation for the result of the homomorphic operation, and performing one of the following based on the determination;
in response to a determination the modulus switching should be performed, performing the modulus switching operation on the result of the homomorphic operation and resetting the noise estimate to a base estimate;
orin response to a determination the modulus switching operation should not be performed, continuing processing with the result without performing the modulus switching operation.
2 Assignments
0 Petitions
Accused Products
Abstract
Homomorphic evaluations of functions are performed. The functions include operation(s). Variants of key switching and modulus switching are described and are performed prior to or after the operation(s). A key switching transformation converts a ciphertext with respect to a first secret key and a first modulus to a ciphertext with respect to a second secret key and a second modulus. A key switching transformation converts a first version of a ciphertext with respect to a first secret key and with some number r bits of precision to a second version of the selected ciphertext with respect to a second keys and with some other number r′ bits of precision. The ciphertexts may be operated on as polynomials represented using evaluation representation, which has benefits for multiplication and automorphism. Further, ciphertexts are associated with an estimate of noise, which is used to determine when to perform modulus switching on the ciphertexts.
-
Citations
20 Claims
-
1. A computer-implemented method, comprising:
-
performing at a computer system homomorphic evaluation of a function on one or more input ciphertexts, where the one or more input ciphertexts were encrypted using a public key of an encryption scheme that also comprises a plurality of secret keys and a plurality of moduli, where the moduli are integers, where the function comprises one or more homomorphic operations, and where performing the homomorphic evaluation comprises performing each of the one or more homomorphic operations for the function, and where performing each of the one or more homomorphic operations comprises; selecting one or more ciphertexts and determining an estimate of noise in the selected one or more ciphertexts; for each one of the selected one or more ciphertexts, in response to a determination the noise magnitude meets at least one criterion, performing a modulus switching operation on the ciphertext to convert the ciphertext from one of the plurality of secret keys and a first modulus into a second ciphertext with respect to a same secret key but a second modulus, and updating the noise estimate following the modulus switching operation; performing the homomorphic operation for the function on the selected one or more ciphertexts; computing the noise estimate for the result of the homomorphic operation from the noise estimate of the selected one or more ciphertexts; determining based on the noise estimate whether to perform a modulus switching operation for the result of the homomorphic operation, and performing one of the following based on the determination; in response to a determination the modulus switching should be performed, performing the modulus switching operation on the result of the homomorphic operation and resetting the noise estimate to a base estimate;
orin response to a determination the modulus switching operation should not be performed, continuing processing with the result without performing the modulus switching operation. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. A computer system, comprising:
-
one or more memories comprising computer-readable program code; and one or more processors, wherein the one or more processors are configured, responsive to execution of the computer-readable program code, to cause the computer system to perform; performing at a computer system homomorphic evaluation of a function on one or more input ciphertexts, where the one or more input ciphertexts were encrypted using a public key of an encryption scheme that also comprises a plurality of secret keys and a plurality of moduli, where the moduli are integers, where the function comprises one or more homomorphic operations, and where performing the homomorphic evaluation comprises performing each of the one or more homomorphic operations for the function, and where performing each of the one or more homomorphic operations comprises; selecting one or more ciphertexts and determining an estimate of noise in the selected one or more ciphertexts; for each one of the selected one or more ciphertexts, in response to a determination the noise magnitude meets at least one criterion, performing a modulus switching operation on the ciphertext to convert the ciphertext from one of the plurality of secret keys and a first modulus into a second ciphertext with respect to a same secret key but a second modulus, and updating the noise estimate following the modulus switching operation; performing the homomorphic operation for the function on the selected one or more ciphertexts; computing the noise estimate for the result of the homomorphic operation from the noise estimate of the selected one or more ciphertexts; and determining based on the noise estimate whether to perform a modulus switching operation for the result of the homomorphic operation, and performing one of the following based on the determination; in response to a determination the modulus switching should be performed, performing the modulus switching operation on the result of the homomorphic operation and resetting the noise estimate to a base estimate;
orin response to a determination the modulus switching operation should not be performed, continuing processing with the result without performing the modulus switching operation. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
-
17. A computer program product comprising a non-transitory computer readable storage medium having program code embodied therewith, the program code readable and executable by a computer to cause the computer to perform:
performing at a computer system homomorphic evaluation of a function on one or more input ciphertexts, where the one or more input ciphertexts were encrypted using a public key of an encryption scheme that also comprises a plurality of secret keys and a plurality of moduli, where the moduli are integers, where the function comprises one or more homomorphic operations, and where performing the homomorphic evaluation comprises performing each of the one or more homomorphic operations for the function, and where performing each of the one or more homomorphic operations comprises; selecting one or more ciphertexts and determining an estimate of noise in the selected one or more ciphertexts; for each one of the selected one or more ciphertexts, in response to a determination the noise magnitude meets at least one criterion, performing a modulus switching operation on the ciphertext to convert the ciphertext from one of the plurality of secret keys and a first modulus into a second ciphertext with respect to a same secret key but a second modulus, and updating the noise estimate following the modulus switching operation; performing the homomorphic operation for the function on the selected one or more ciphertexts; computing the noise estimate for the result of the homomorphic operation from the noise estimate of the selected one or more ciphertexts; and determining based on the noise estimate whether to perform a modulus switching operation for the result of the homomorphic operation, and performing one of the following based on the determination; in response to a determination the modulus switching should be performed, performing the modulus switching operation on the result of the homomorphic operation and resetting the noise estimate to a base estimate;
orin response to a determination the modulus switching operation should not be performed, continuing processing with the result without performing the modulus switching operation. - View Dependent Claims (18, 19, 20)
Specification