International Business Machines Corporation

Leland Stanford Junior University

The University of Bristol

Craig B Gentry

Shai Halevi

Nigel P Smart

Vinod Vaikuntanathan

Charanjit Singh Jutla

Nibel P Smart

A request is received for specific information that can be determined using data in a database on a first computer system. Either at least some of the data is encrypted or the request is encrypted. The first computer system does not have a decryption key to decrypt the encrypted data or request. The first computer system performs compressible HE operations on the data to determine compressed ciphertext(s) that correspond to the specific information. The operations include using a first uncompressed HE scheme and a second compressed HE scheme. The first HE scheme is used on the data to create other multiple ciphertexts and the second HE scheme is used on the other multiple ciphertexts to pack the other multiple ciphertexts into fewer ciphertexts that are compressed. Both the HE schemes use a same secret key. The first computer system sends a response including compressed ciphertext(s) corresponding to the specific information.

Compressible (F)HE with applications to PIR

A request is received for specific information that can be determined using data in a database on a first computer system. Either at least some of the data is encrypted or the request is encrypted. The first computer system does not have a decryption key to decrypt the encrypted data or request. The first computer system performs compressible HE operations on the data to determine compressed ciphertext(s) that correspond to the specific information. The operations include using a first uncompressed HE scheme and a second compressed HEscheme. The first HE scheme is used on the data to create other multiple ciphertexts and the second HE scheme is used on the other multiple ciphertexts to pack the other multiple ciphertexts into fewer ciphertexts that are compressed. Both the HE schemes use a same secret key. The first computer system sends a response including compressed ciphertext(s) corresponding to the specific information.

A method for compiling a matrix-product program into an obfuscated-matrix-product program includes receiving a plurality of matrices that form the matrix-product program, randomly generating a set of independent and invertible tensor-product matrices, randomly generating a set of independent and invertible linear-transform matrices, and generating a dynamic-fence-generation gadget by processing at least one of the plurality of matrices, the set of tensor-product matrices and the set of linear-transform matrices. The dynamic-fence-generation gadget is an obfuscated version of computer program represented by the plurality of matrices.

Obfuscating programs using matrix tensor products

In one exemplary embodiment of the invention, a method for computing a resultant and a free term of a scaled inverse of a first polynomial v(x) modulo a second polynomial f(x), including: receiving the first polynomial v(x) modulo the second polynomial f(x), where the second polynomial is of a form f(x)=x&#xb1;1, where n=2and k is an integer greater than 0; computing lowest two coefficients of a third polynomial g(z) that is a function of the first polynomial and the second polynomial, where where &#x3c1;, &#x3c1;, . . . , &#x3c1;are roots of the second polynomial f(x) over a field; outputting the lowest coefficient of g(z) as the resultant; and outputting the second lowest coefficient of g(z) divided by n as the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f(x).

Fast computation of a single coefficient in an inverse polynomial

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.

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

Homomorphic evaluation of a function is performed on input ciphertext(s), which were encrypted using a public key of an encryption scheme that also includes multiple secret keys and multiple integer moduli. The homomorphic evaluation of the function includes performing operations(s) on the input ciphertexts. The function includes operation(s) including one or more of addition, multiplication, and automorphism. A key-switching transformation is performed on selected input ciphertext(s), and includes converting a first version of a selected ciphertext with respect to a first of the multiple secret keys and a first modulus to a second version of the selected ciphertext with respect to a second of the multiple secret keys and a second modulus, where the second modulus is an integer factor p times the first modulus, p&#x3e;1. Each of the key switching transformations is performed prior to or after the operation(s) are evaluated. Results of the operation(s) are output.

In one exemplary embodiment of the invention, a method and computer program include: receiving first and second ciphertexts having first and second data encrypted per an encryption scheme, the encryption scheme has public/secret keys and encryption, decryption, operation and refresh functions, the encryption function encrypts data, the decryption decrypts ciphertext, the operation receives ciphertexts and performs operation(s) on them, the refresh operates to prevent growth of the magnitude of noise for a ciphertext while reducing the modulus of the ciphertext without using the secret key, utilizing a modulus switching technique that involves transforming a first ciphertext c modulo q into a second ciphertext c' modulo p while preserving correctness, the technique includes scaling by p/q and rounding, p&#x3c;q; using the operation function(s), performing operation(s) on them to obtain a third ciphertext; and reducing a noise level of the third ciphertext using the refresh function.

Fully homomorphic encryption

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 pof the modulus q and each column j corresponding to a polynomial factor F(X) of the m-th cyclotomic polynomial &#x3a6;(X) modulo q. Content of the matrix in row i and column j corresponds to the element a(X) modulo pand F(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.

Homomorphic evaluation of a function is performed on input ciphertext(s), which were encrypted using a public key of an encryption scheme that also includes multiple secret keys. Each input ciphertext includes multiple real numbers that are kept with finite precision. Performing the homomorphic evaluation of the function includes performing operation(s). Performing each of one or more operations includes the following. A key-switching transformation is performed on selected ciphertext(s), including converting a first version of a selected ciphertext with respect to a first of the secret keys and with some number r bits of precision to a second version of the selected ciphertext with respect to a second of the secret keys and with some other number r' bits of precision, r&#x2032;&#x3e;r. Each key switching transformation is performed prior to or after the operation(s) are evaluated. Results of the operation(s) are output.

In one exemplary embodiment, a computer readable storage medium tangibly embodying a program of instructions executable by a machine for performing operations including: receiving information B to be encrypted as a ciphertext C in accordance with an encryption scheme having an encrypt function; and encrypting B in accordance with the encrypt function to obtain C, the scheme utilizes at least one public key A, where B, C, and A are matrices, the encrypt function receives as inputs A and B and outputs C as C&#x2190;AS+pX+B(mod q), S is a random matrix, X is an error matrix, p is in integer, q is an odd prime number. In other exemplary embodiments, the encryption scheme includes a decrypt function that receives as inputs at least one private key T (a matrix) and C and outputs B as B=T&#xb7;(TCTmod q)&#xb7;(T)mod p.

Efficient homomorphic encryption scheme for bilinear forms

In one exemplary embodiment of the invention, a method for computing a resultant and a free term of a scaled inverse of a first polynomial v(x) modulo a second polynomial f(x), including: receiving the first polynomial v(x) modulo the second polynomial f(x), where the second polynomial is of a form f(x)=x&#xb1;1, where n=2and k is an integer greater than 0; computing lowest two coefficients of a third polynomial g(z) that is a function of the first polynomial and the second polynomial, where g(z)&#x3a0;(v(&#x3c1;)&#x2212;z), where &#x3c1;, &#x3c1;, . . . , &#x3c1;are roots of the second polynomial f(x) over a field; outputting the lowest coefficient of g(z) as the resultant; and outputting the second lowest coefficient of g(z) divided by n as the free term of the scaled inverse of the first polynomial v(x) modulo the second polynomial f(x).

Growing community of inventors

New York, NY, United States of America

Craig B Gentry