Fully homomorphic encryption

Patent metadata

Field	Value
Publication number	US-9716590-B2
Application number	US-201514740354-A
Country	US
Kind code	B2
Filing date	Jun 16, 2015
Priority date	Apr 29, 2011
Publication date	Jul 25, 2017
Grant date	Jul 25, 2017

Abstract

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

First claim

What is claimed is:

1. A non-transitory computer-readable storage medium for secure multiparty computation and communication and storing program instructions, execution of the program instructions resulting in operations comprising:
receiving, over a network and as part of a secure multiparty computation and communication process, at a server computer system a query from a requestor computer system;
performing, as part of the secure multiparty computation and communication process, a fully homomorphic encryption scheme allowing the server computer system to perform homomorphic operations on input ciphertexts without decrypting the ciphertexts and based on the query, to produce one or more results that when decrypted are an answer to the query, wherein performing the fully homomorphic encryption scheme comprises:
accessing, at the server computer system and from a memory of the server computer system, a plurality of input ciphertexts, where each of the input ciphertexts comprises data encrypted in accordance with the fully homomorphic encryption scheme, where the fully homomorphic encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two given ciphertexts and uses the public key to perform at least one operation on the at least two given ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of a magnitude of noise for a provided ciphertext while reducing a modulus of the provided ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming the provided ciphertext c modulo q into another ciphertext c′ modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the fully homomorphic encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the fully homomorphic encryption scheme;
determining, by the server computer system, from the plurality of input ciphertexts the one or more results corresponding to and satisfying the query by performing homomorphic operations using at least the plurality of input ciphertexts at least by:
performing operations on ciphertexts according to a circuit that corresponds to the query and the evaluation of which produces the one or more results that satisfy the query, wherein the operations use the at least one operation function to obtain a ciphertext result, and wherein at least some of the operations involve the plurality of input ciphertexts;
reducing a noise level of the ciphertext result by using the refresh function; and
determining the one or more results of the evaluation of the circuit at least by evaluating the circuit and iterating the performing the operations and the reducing the noise level multiple times during the evaluation of the circuit; and

completing the secure multiparty computation and communication process at least by sending by the server computer system and over the network the one or more results of the evaluation of the circuit to the requestor computer system.

2. The non-transitory computer-readable storage medium of claim 1 , where application of the refresh function to the provided ciphertext also reduces a range of coefficients for an output of the refresh function, relative to a range of coefficients for the provided ciphertext.

3. The non-transitory computer-readable storage medium of claim 1 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being performed the refresh function is applied to an output of the multiplication.

4. The non-transitory computer-readable storage medium of claim 1 , where the at least one operation comprises at least one of an addition and a multiplication, where in response to a multiplication being desired the refresh function is applied to at least one input of the multiplication.

5. The non-transitory computer-readable storage medium of claim 1 , where the fully homomorphic encryption scheme enables evaluation of a polynomial depth circuit of multiplications and wherein the circuit that corresponds to the query comprises the polynomial depth circuit of multiplications.

6. A method for secure multiparty computation and communication, comprising:
receiving, over a network and as part of a secure multiparty computation and communication process, at a server computer system a query from a requestor computer system;
performing, as part of the secure multiparty computation and communication process, a fully homomorphic encryption scheme allowing the server computer system to perform homomorphic operations on input ciphertexts without decrypting the ciphertexts and based on the query, to produce one or more results that when decrypted are an answer to the query, wherein performing the fully homomorphic encryption scheme comprises:
accessing, at the server computer system and from a memory of the server computer system, a plurality of input ciphertexts, where each of the input ciphertexts comprises data encrypted in accordance with the fully homomorphic encryption scheme, where the encryption scheme uses a public key and a secret key and includes an encryption function, a decryption function, at least one operation function and a refresh function, where the encryption function operates to obtain ciphertext by encrypting data using the public key, where the decryption function operates using the secret key to decrypt ciphertext for data encrypted using the public key and obtain the data, where the at least one operation function receives at least two given ciphertexts and uses the public key to perform at least one operation on the at least two given ciphertexts and obtain a resulting ciphertext, where the refresh function operates to prevent growth of a magnitude of noise for a provided ciphertext while reducing a modulus of the provided ciphertext without using the secret key, where the refresh function utilizes a modulus switching technique that comprises transforming the provided ciphertext c modulo q to another ciphertext c′ modulo p while preserving correctness, where the modulus switching technique includes scaling by p/q and rounding, where p<q, where the fully homomorphic encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the fully homomorphic encryption scheme;
determining, by the server computer system, from the plurality of input ciphertexts the one or more results corresponding to and satisfying the query by performing homomorphic operations using at least the plurality of input ciphertexts at least by:
performing operations on ciphertexts according to a circuit that corresponds to the query and the evaluation of which produces the one or more results that satisfy the query, wherein the operations use the at least one operation function to obtain a ciphertext result, and wherein at least some of the operations involve the plurality of input ciphertexts;
reducing a noise level of the ciphertext result by using the refresh function; and
determining the one or more results of the evaluation of the circuit at least by evaluating the circuit and iterating the performing the operations and the reducing the noise level multiple times during the evaluation of the circuit; and

completing the secure

Assignees

• IBM

Inventors

• Gentry Craig B

Classifications

• H04L9/28 Primary

  Electricity · mapped topic

• H04L9/008 Primary

  involving homomorphic encryption · CPC title

• H04L9/3093

  involving Lattices or polynomial equations, e.g. NTRU scheme · CPC title

• H04L2209/08

  Randomization, e.g. dummy operations or using noise · CPC title