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

Patent metadata

Field	Value
Publication number	US-9281941-B2
Application number	US-201313746713-A
Country	US
Kind code	B2
Filing date	Jan 22, 2013
Priority date	Feb 17, 2012
Publication date	Mar 8, 2016
Grant date	Mar 8, 2016

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 method, comprising:
Performing, by a computing device, 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, and where performing the homomorphic evaluation of the function comprises performing one or more operations on the input ciphertexts, where the function comprises one or multiple operations comprising one of more of addition, multiplication, and automorphism;
Performing a key-switching transformation on selected ones of the one or more input ciphertexts, where performing a key-switching transformation on a selected ciphertext comprises converting a first version of the selected ciphertext with respect to a first of the plurality of secret keys and a first modulus to a second version of the selected ciphertext with respect to a second of the plurality of secret keys and a second secret modulus, where the second modulus is an integer factor p times the first modulus, where p>1,
Where each of the key switching transformations is performed prior to or after the one or more operations are evaluated; and outputting one or more results of the one or more operations.

2. The method of claim 1 , further comprising, subsequent to the key switching transformation, switching, using the second version of the selected ciphertext, the second modulus to a third modulus, which can be equal to or different from the first modulus, to determine a third version of the selected ciphertext with respect to the second secret key and the third modulus.

3. The method of claim 1 , where the portion of the public key used for the performing the key switching transformation is a matrix W=W[ps′→s] modulo pq, where the matrix W is included in the public key, s′ is the first secret key, s is the second secret key, p is the integer factor, and q is a value of the first modulus.

4. The method of claim 3 , where performing a key switching transformation comprises setting c=W·c′ modulo pq, where c′ is the first version of the selected ciphertext and c is the second version of the selected ciphertext.

5. The method of claim 1 , where the integer factor p is larger than q, where q is the first modulus.

6. The method of claim 1 , where q is the first modulus, where performing the homomorphic evaluation further comprises, prior to performing the key switching transformation, decreasing a norm of the first version of the selected ciphertext, by representing every number in the selected ciphertext as a sum of a number d>1 of smaller digits, and were the integer factor p is larger than q 1/d .

7. A computer program product comprising a computer readable storage device having program code embodied therewith, the program code readable/executable by a computer to perform
a method, comprising:
Performing, by a computing device, 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, and where performing the homomorphic evaluation of the function comprises performing one or more operations on the input ciphertexts, where the function comprises one or multiple operations comprising one of more of addition, multiplication, and automorphism;
Performing a key-switching transformation on selected ones of the one or more input ciphertexts, where performing a key-switching transformation on a selected ciphertext comprises converting a first version of the selected ciphertext with respect to a first of the plurality of secret keys and a first modulus to a second version of the selected ciphertext with respect to a second of the plurality of secret keys and a second secret modulus, where the second modulus is an integer factor p times the first modulus, where p>1,
Where each of the key switching transformations is performed prior to or after the one or more operations are evaluated; and outputting one or more results of the one or more operations.

Assignees

• IBM
• Univ Bristol

Inventors

• Gentry Craig B
• Halevi Shai
• Smart Nigel P

Classifications

• H04L9/08 Primary

  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 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/0618

  Block ciphers, i.e. encrypting groups of characters of a plain text message using fixed encryption transformation · 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