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

• US 9,621,346 B2
• Filed: 01/28/2016
• Issued: 04/11/2017
• Est. Priority Date: 02/17/2012
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation, University of Bristol
• Original Assignee: International Business Machines Corporation
• Inventors: Smart, Nibel P., Gentry, Craig B., Halevi, Shai
• Primary Examiner(s): Wang, Harris C
• Application Number:
  US15/009,133
• Publication Number:
  US 20160164671A1
• Time in Patent Office: 439 Days
• Field of Search: 380 28
• 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

A homomorphic evaluation of a function is performed on input ciphertext(s), which were encrypted using an encryption scheme that includes multiple integer moduli. Each ciphertext contains one or more elements of an m-th cyclotomic number field, where m is an integer. Each ciphertext which is defined relative to one of the moduli q, each element a(X) of the m-th cyclotomic number field is represented via a matrix, with each row i of the matrix corresponding to an integer factor p_i of the modulus q and each column j corresponding to a polynomial factor F_j(X) of the m-th cyclotomic polynomial Φ_m(X) modulo q. Content of the matrix in row i and column j corresponds to the element a(X) modulo p_i and F_j(X). Performing the homomorphic evaluation of the function further includes performing operation(s) using one or more matrices from one or more of the ciphertexts.

Claims

1. A method, comprising:

performing, by a computing device, a homomorphic evaluation of a function on one or more input ciphertexts, where the one or more input ciphertexts were encrypted using an encryption scheme that includes a plurality of integer moduli, where each ciphertext contains one or more elements of an m-th cyclotomic number field, where m is an integer, where each ciphertext which is defined relative to one of the moduli q, each element a(X) of the m-th cyclotomic number field is represented via a matrix, with each row i of the matrix corresponding to an integer factor p_i of the modulus q and each column j corresponding to a polynomial factor F_j(X) of the m-th cyclotomic polynomial Φ

_m(X) modulo q, and where content of the matrix in row i and column j corresponds to the element a(X) modulo p_i and F_j(X), and where performing the homomorphic evaluation of the function further comprises performing one or more operations using one or more matrices from one or more of the ciphertexts.

2. The method of claim 1, where the one or more operations comprise homomorphic multiplication operations of two ciphertexts performed by entry-by-entry multiplication of matrices from the two ciphertexts.

3. The method of claim 1, where the one or more operations comprise automorphism of a ciphertext performed by permuting columns of the matrices from the ciphertext.

4. The method of claim 1, where the plurality of moduli consist of products of smaller primes p_i, where the t-th modulus q_t is the product of the first t smaller primes, q_t=Π

_i=1^tp_i.

5. The method of claim 4, where for each small prime p_i, p_i−

1 is divisible by m, where m is an integer defining the m-th cyclotomic number field.

6. The method of claim 4, where the one or more operations comprise performing a modulus switching operation from q_t to q_t-1 on a ciphertext, and where performing the modulus switching operation comprises scaling down each element a(X) of the m-th cyclotomic number field in the ciphertext by a factor of p_t=q_t/q_t-1, where the operation of scaling comprises:

setting ā

(X) to be a coefficient representation of a(X) mod p_t;

adding or subtracting multiplies of p_t to every coefficient of ā

(X), thereby obtaining a polynomial δ

(X) where all the coefficients of δ

(X) are divisible by an integer r, where r is co-prime with p_t;

computing the representation the polynomial δ

(X) by a matrix of elements δ

_ij(X), where the element in row i and column j of the matrix is computed as δ

(X) modulo the i'"'"'th small prime p_i and the j'"'"'th polynomial factor F_j(X) of the cyclotomic polynomial Φ

_m(X) modulo p_i, δ

_ij(X)=δ

(X) mod (p_i,F_j(X));

subtracting δ

(X) from a(X), setting ã

(X)=a(X)−

δ

(X); and

dividing ã

(X) by p_t, setting a′

(X)=ã

(X)/p_t, and outputting a′

(X).

7. 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 a homomorphic evaluation of a function on one or more input ciphertexts, where the one or more input ciphertexts were encrypted using an encryption scheme that includes a plurality of integer moduli, where each ciphertext contains one or more elements of an m-th cyclotomic number field, where m is an integer, where each ciphertext which is defined relative to one of the moduli q, each element a(X) of the m-th cyclotomic number field is represented via a matrix, with each row i of the matrix corresponding to an integer factor p_i of the modulus q and each column j corresponding to a polynomial factor F_j(X) of the m-th cyclotomic polynomial Φ

_m(X) modulo q, and where content of the matrix in row i and column j corresponds to the element a(X) modulo p_i and F_j(X), and where performing the homomorphic evaluation of the function further comprises performing one or more operations using one or more matrices from one or more of the ciphertexts.

8. The computer system of claim 7, where the one or more operations comprise homomorphic multiplication operations of two ciphertexts performed by entry-by-entry multiplication of matrices from the two ciphertexts.

9. The computer system of claim 7, where the one or more operations comprise automorphism of a ciphertext performed by permuting columns of the matrices from the ciphertext.

10. The computer system of claim 7, where the plurality of moduli consist of products of smaller primes p_i, where the t-th modulus q_t is the product of the first t smaller primes, q_t=Π

_i=1^tp_i.

11. The computer system of claim 10, where for each small prime p_i, p_i−

1 is divisible by m, where m is an integer defining the m-th cyclotomic number field.

12. The computer system of claim 10, where the one or more operations comprise performing a modulus switching operation from q_t to q_t-1 on a ciphertext, and where performing the modulus switching operation comprises scaling down each element a(X) of the m'"'"'th cyclotomic number field in the ciphertext by a factor of p_t=q_t/q_t-1, where the operation of scaling comprises:

setting ā

(X) to be a coefficient representation of a(X) mod p_t;

performing one of adding or subtracting p_t from every odd coefficient of ā

(X), thereby obtaining a polynomial δ

(X) with coefficients in (−

p_t, p_t];

computing the representation the polynomial δ

(X) by a matrix of elements δ

_ij(X), where the element in row i and column j of the matrix is computed as δ

(X) modulo the i'"'"'th small prime p_i and the j'"'"'th polynomial factor F_j(X) of the cyclotomic polynomial Φ

_m(X) modulo p_i, δ

_ij(X)=δ

(X) mod (p_i,F_j(X));

subtracting δ

(X) from a(X), setting ã

(X)=a(X)−

δ

(X); and

dividing ã

(X) by p_t, setting a′

(X)=ã

(X)/p_t, and outputting a′

(X).

17. The method of claim 7, wherein:

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

the performing the 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.

18. The method of claim 17, wherein:

the computing device comprises a server residing on the Internet;

the server comprises one or more communications components; and

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

19. The computer system of claim 7, 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 the 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.

20. The computer system of claim 19, 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.

13. 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 a homomorphic evaluation of a function on one or more input ciphertexts, where the one or more input ciphertexts were encrypted using an encryption scheme that includes a plurality of integer moduli, where each ciphertext contains one or more elements of an m-th cyclotomic number field, where m is an integer, where each ciphertext which is defined relative to one of the moduli q, each element a(X) of the m-th cyclotomic number field is represented via a matrix, with each row i of the matrix corresponding to an integer factor p_i of the modulus q and each column j corresponding to a polynomial factor F_j(X) of the m-th cyclotomic polynomial Φ

_m(X) modulo q, and where content of the matrix in row i and column j corresponds to the element a(X) modulo p_i and F_j(X), and where performing the homomorphic evaluation of the function further comprises performing one or more operations using one or more matrices from one or more of the ciphertexts.

14. The computer program product of claim 13, where the plurality of moduli consist of products of smaller primes p_i, where the t-th modulus q_t is the product of the first t smaller primes, q_t=Π

_i=1^tp_i, and where for each small prime p_i, p_i−

1 is divisible by m, where m is an integer defining the m-th cyclotomic number field.

15. The computer program product of claim 13, where the plurality of moduli consist of products of smaller primes p_i, where the t-th modulus q_t is the product of the first t smaller primes, q_t=Π

_i=1^tp_i, where the one or more operations comprise performing a modulus switching operation from q_t to q_t-1 on a ciphertext, and where performing the modulus switching operation comprises scaling down each element a(X) of the m'"'"'th cyclotomic number field in the ciphertext by a factor of p_t=q_t/q_t-1, where the operation of scaling comprises;

setting ā

(X) to be a coefficient representation of a(X) mod p_t;

performing one of adding or subtracting p_t from every odd coefficient of ā

(X), thereby obtaining a polynomial δ

(X) with coefficients in (−

p_t, p_t];

computing the representation the polynomial δ

(X) by a matrix of elements δ

_ij(X), where the element in row i and column j of the matrix is computed as δ

(X) modulo the i'"'"'th small prime p_i and the j'"'"'th polynomial factor F_j(X) of the cyclotomic polynomial Φ

_m(X) modulo p_i, δ

_ij(X)=δ

(X) mod (p_i, F_j(X));

subtracting δ

(X) from a(X), setting ã

(X)=a(X)−

δ

(X); and

dividing ã

(X) by p_t, setting a′

(X)=ã

(X)/p_t, and outputting a′

(X).

16. The computer program product of claim 13, where the plurality of moduli consist of products of smaller primes p_i, where the t-th modulus q_t is the product of the first t smaller primes, q_t=Π

_i=1^tp_i, where the one or more operations comprise performing a modulus switching operation from q_t to q_t-1 on a ciphertext, and where performing the modulus switching operation comprises scaling down each element a(X) of the m-th cyclotomic number field in the ciphertext by a factor of p_t=q_t/q_t-1, where the operation of scaling comprises;

setting ā

(X) to be a coefficient representation of a(X) mod p_t;

adding or subtracting multiplies of p_t to every coefficient of ā

(X), thereby obtaining a polynomial δ

(X) where all the coefficients of δ

(X) are divisible by an integer r, where r is co-prime with p_t;

computing the representation the polynomial δ

(X) by a matrix of elements δ

_ij(X), where the element in row i and column j of the matrix is computed as δ

(X) modulo the i'"'"'th small prime p_i and the j'"'"'th polynomial factor F_j(X) of the cyclotomic polynomial Φ

_m(X) modulo p_i, δ

_ij(X)=δ

(X) mod (p_i,F_j(X));

subtracting δ

(X) from a(X), setting ã

(X)=a(X)−

δ

(X); and

dividing ã

(X) by p_t, setting a′

(X)=ã

(X)/p_t, and outputting a′

(X).