Homomorphic evaluation including key switching, modulus switching, and dynamic noise management

• US 10,057,057 B2
• Filed: 10/17/2016
• Issued: 08/21/2018
• Est. Priority Date: 02/17/2012
• Status: Active Grant

• Current Assignee: International Business Machines Corporation, University of Bristol
• Original Assignee: International Business Machines Corporation
• Inventors: Gentry, Craig B., Halevi, Shai, Smart, Nigel P.
• Primary Examiner(s): King, John B
• Application Number:
  US15/294,967
• Publication Number:
  US 20180109376A1
• Time in Patent Office: 673 Days
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 63/0442 wherein the sending and receiving network entities apply asymmetric encryption, i.e. different keys for encryption and decryption cryptographic mechanisms or cryptographic arrangements for public-key encryption H04L9/30
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0618 Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation
• CPC Class Codes: H04L 9/08 Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords network architectures or network communication protocols for supporting key management in a packet data network H04L63/06
• CPC Class Codes: H04L 9/0838 Key agreement, i.e. key establishment technique in which a shared key is derived by parties as a function of information contributed by, or associated with, each of these network architectures or network communication protocols for key exchange in a packet data network H04L63/061
• CPC Class Codes: H04L 9/16 the keys or algorithms being changed during operation
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy
• CPC Class Codes: H04L 9/38 Encryption being effected by mechanical apparatus, e.g. rotating cams, switches, keytape punchers

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.

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;

or

in response to a determination the modulus switching operation should not be performed, continuing processing with the result without performing the modulus switching operation.

2. The method of claim 1, wherein computing the noise estimate comprises computing for the homomorphic operation of multiply-by-constant the following equation:

v′

=|k|·

v, where the noise estimate of the selected one or more ciphertexts is v and the noise estimate for the result of the multiply-by-constant operation is v′

, where |k| is a constant, |k|≈

ϕ

(m)/2 is a magnitude of the constant, and ϕ

(m) is a number of vectors in a selected distribution of samples from a ring of integers of an mth cyclotomic number field.

3. The method of claim 1, wherein computing the noise estimate comprises computing for the homomorphic operation of multiplication the following equation:

v′

=v₁·

v₂·

√

{square root over (ϕ

(m))}, where the noise estimate of one multiplicand ciphertext is v₁, the noise estimate of another multiplicand ciphertext is v₂, and the noise estimate for the result of the multiplication is v′

, and ϕ

(m) is a number of vectors in a selected distribution of samples from a ring of integers of an mth cyclotomic number field.

4. The method of claim 3, wherein computing the noise estimate comprises computing for the homomorphic operation of key-switching the following equation:

v′

=p·

v+B_ks, where the noise estimate of a selected ciphertext is v and the noise estimate for the result of the homomorphic operation is v′

, where B_ks≈

9σ

ϕ

(m)·

q_t, where σ

² is a variance that is used when generating error polynomials, q_t represents an estimate of a size of the result of the key-switching, where ϕ

(m) is a number of vectors in a selected distribution of samples from a ring of integers of an mth cyclotomic number field, and where p is an integer factor used in the key-switching operation.

5. The method of claim 1, wherein computing the noise estimate comprises computing for the homomorphic operation of addition the following equation:

v′

=v₁+v₂, where the noise estimate of one ciphertext in the addition is v₁, the noise estimate of another ciphertext in the addition is v₂, and the noise estimate for the result of the addition is v′

.

6. The method of claim 1, wherein computing the noise estimate comprises computing for the homomorphic operation of automorphism the following equation:

v′

=v, where the noise estimate of the one selected ciphertext in the automorphism is v and the noise estimate for the result of the automorphism is v′

.

7. The method of claim 1, wherein:

the method further comprises receiving at the computer system a query from a requestor computer system;

the performing at the computer system homomorphic evaluation of the function is performed one or more times to evaluate a circuit using the query, the query corresponds to the input ciphertexts, and evaluation of the circuit produces one or more results; and

the method further comprises sending the one or more results of the evaluation of the circuit to the requestor computer system for decryption by the requestor computer system.

8. The method of claim 7, further comprising:

transmitting by the requestor computer system a query to the computer system performing the homomorphic evaluation of the function; and

receiving by the requestor computer system the one or more results and decrypting by the requestor computer system the one or more results to determine an answer to the query.

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;

or

in response to a determination the modulus switching operation should not be performed, continuing processing with the result without performing the modulus switching operation.

10. The computer system of claim 9, where the determination the noise magnitude meets at least one criterion occurs in response to noise magnitude being greater than a threshold.

11. The computer system of claim 9, wherein updating the noise estimate following the modulus switching operation comprises computing the following equation:

v′

=v(q_t/q<sub>t−

1</sub>)+B_scale, where the noise estimate of the one selected ciphertext is v and the noise estimate for the result of the modulus switching operation is v′

, B_scale is a constant, q_t is the second modulus after the key-switching operation, q<sub>t−

1</sub> is the first modulus before the key-switching operation, and B_scale≈

√

{square root over (ϕ

(m)·

h)}, where ϕ

(m) is a number of vectors in a selected distribution of samples from a ring of integers of an mth cyclotomic number field, and where h is a Hamming weight of the one secret key.

12. The computer system of claim 9, wherein computing the noise estimate comprises computing for the homomorphic operation of multiplication the following equation:

v′

=v₁·

v₂·

√

{square root over (ϕ

(m))}, where the noise estimate of one multiplicand ciphertext is v₁, the noise estimate of another multiplicand ciphertext is v₂, and the noise estimate for the result of the multiplication is v′

, and ϕ

(m) is a number of vectors in a selected distribution of samples from a ring of integers of an mth cyclotomic number field.

13. The computer system of claim 12, wherein computing the noise estimate comprises computing for the homomorphic operation of key-switching the following equation:

v′

=p·

v+B_ks, where the noise estimate of a selected ciphertext is v and the noise estimate for the result of the homomorphic operation is v′

, where B_ks≈

9σ

ϕ

(m)·

q_t, where σ

² is a variance that is used when generating error polynomials, q_t represents an estimate of a size of the result of the key-switching, where ϕ

(m) is a number of vectors in a selected distribution of samples from a ring of integers of an mth cyclotomic number field, and where p is an integer factor used in the key-switching operation.

14. The computer system of claim 9, wherein computing the noise estimate comprises computing for the homomorphic operation of automorphism the following equation:

v′

=v, where the noise estimate of the one selected ciphertext in the automorphism is v and the noise estimate for the result of the automorphism is v′

.

15. The computer system of claim 9, wherein:

the one or more processors are further configured, responsive to execution of the computer-readable program code, to cause the computer system to perform;

receiving at the computer system a query from a requestor computer system;

the performing at the computer system homomorphic evaluation of the function is performed one or more times to evaluate a circuit using the query, the query corresponds to the input ciphertexts, and evaluation of the circuit produces one or more results; and

the one or more processors are further configured, responsive to execution of the computer-readable program code, to cause the computer system to perform;

sending the one or more results of the evaluation of the circuit to the requestor computer system for decryption by the requestor computer system.

16. The computer system of claim 15, wherein:

the computer system resides on the Internet;

the computer system comprises one or more communications components; and

the one or more processors are further configured, responsive to execution of the computer-readable program code, to cause the computer system to perform;

communicating by the computer system with the requestor computer system over the Internet using the one or more communications components.

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;

or

in response to a determination the modulus switching operation should not be performed, continuing processing with the result without performing the modulus switching operation.

18. The computer program product of claim 17, wherein updating the noise estimate following the modulus switching operation comprises computing the following equation:

v′

=v(q_t/q<sub>t−

1</sub>)+B_scale, where the noise estimate of the one selected ciphertext is v and the noise estimate for the result of the modulus switching operation is v′

, B_scale is a constant, q_t is the second modulus after the key-switching operation, q<sub>t−

1</sub> is the first modulus before the key-switching operation, and B_scale≈

√

{square root over (ϕ

(m)·

h)}, where ϕ

(m) is a number of vectors in a selected distribution of samples from a ring of integers of an mth cyclotomic number field, and where h is a Hamming weight of the one secret key.

19. The computer program product of claim 17, wherein computing the noise estimate comprises computing for the homomorphic operation of multiply-by-constant the following equation:

v′

=|k|·

v, where the noise estimate of the selected one or more ciphertexts is v and the noise estimate for the result of the multiply-by-constant operation is v′

, where |k| is a constant, |k|≈

ϕ

(m)/2 is a magnitude of the constant, and ϕ

(m) is a number of vectors in a selected distribution of samples from a ring of integers of an mth cyclotomic number field.

20. The computer program product of claim 17, wherein computing the noise estimate comprises computing for the homomorphic operation of addition the following equation:

v′

=v₁+v₂, where the noise estimate of one ciphertext in the addition is v₁, the noise estimate of another ciphertext in the addition is v₂, and the noise estimate for the result of the addition is v′

.