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

Patent metadata

Field	Value
Publication number	US-10057057-B2
Application number	US-201615294967-A
Country	US
Kind code	B2
Filing date	Oct 17, 2016
Priority date	Feb 17, 2012
Publication date	Aug 21, 2018
Grant date	Aug 21, 2018

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.

First claim

What is claimed is:

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 1 ·v 2 ·√{square root over (ϕ(m))}, where the noise estimate of one multiplicand ciphertext is v 1 , the noise estimate of another multiplicand ciphertext is v 2 , 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 σ 2 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 1 +v 2 , where the noise estimate of one ciphertext in the addition is v 1 , the noise estimate of another ciphertext in the addition is v 2 , 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 tha

Assignees

• IBM
• Univ Bristol

Inventors

• Gentry Craig B
• Halevi Shai
• Smart Nigel P

Classifications

• H04L9/0838 Primary

  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 title

• H04L63/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 title

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L9/38

  Encryption being effected by mechanical apparatus, e.g. rotating cams, switches, keytape punchers · CPC title

• H04L9/16

  the keys or algorithms being changed during operation · CPC title