Homomorphic Evaluation Including Key Switching, Modulus Switching, And Dynamic Noise Management

Patent metadata

Field	Value
Publication number	US-2016164671-A1
Application number	US-201615009133-A
Country	US
Kind code	A1
Filing date	Jan 28, 2016
Priority date	Feb 17, 2012
Publication date	Jun 9, 2016
Grant date	—

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.

First claim

What is claimed is:

1 . A method, comprising:
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.

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 t p 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 ; performing one of adding or subtracting p 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).

7 . 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 1 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).

8 . 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 1 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.

9 . The computer system of claim 8 , 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.

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

11 . The computer system of claim 8 , 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 t p i .

12 . The computer system of claim 11 , 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.

13 . The computer system of claim 11 , 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, 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 1 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).

14 . The computer system of claim 11 , 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), w

Assignees

• IBM
• Univ Bristol

Inventors

• Gentry Craig B
• Halevi Shai
• Smart Nigel P

Classifications

• H04L9/16

  the keys or algorithms being changed during operation · CPC title

• H04L9/008 Primary

  involving homomorphic encryption · 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/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 title

• H04L9/38

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