Fully homomorphic encryption
View Patent ↗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.
1. A non-transitory computer-readable storage medium storing program instructions, execution of the program instructions resulting in operations comprising:
transmitting by a requestor a query to a computer system;
receiving at the computer system the query;
accessing, at the computer system and from a memory of the computer system, a plurality of ciphertexts, where each of the input ciphertexts comprises data encrypted in accordance with an 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 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 encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme;
retrieving, by the computer system and from the memory, 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;
sending by the computer system the one or more results of the evaluation of the circuit to the requestor; and
receiving by the requestor the one or more results and decrypting by the requestor the one or more results to determine an answer to the query.
2. The 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 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 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 computer-readable storage medium of claim 1 , where the encryption scheme enables evaluation of a polynomial depth circuit of multiplications and wherein the circuit that corresponds to the query comprises the polynominal depth circuit of multiplications.
6. A method, comprising:
transmitting by a requestor a query to a computer system;
receiving at a computer system the query;
accessing, at the computer system and from a memory of the computer system, a plurality of input ciphertexts, where each of the input ciphertexts comprises data encrypted in accordance with an 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 into a 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 encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme;
retrieving, by the computer system and from the memory, 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 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;
sending by the computer system the one or more results of the evaluation of the circuit to the requestor; and
receiving by the requestor the one or more results and decrypting by the requestor the one or more results to determine an answer to the query.
7. The method of claim 6 , 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 for the provided ciphertext.
8. The method of claim 6 , 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.
9. The method of claim 6 , 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.
10. The method of claim 6 , where the 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.
11. An apparatus, comprising:
a requestor comprising a first computer system configured to transmit a query to a second computer system;
the second computer system configured to perform the following:
receive a query from a requestor;
access a plurality of input ciphertexts from a memory of the second computer system, the memory configured to store the input ciphertexts, where each of the input ciphertexts comprises data encrypted in accordance with an 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 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 encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme;
where the second computer system is further configured to retrieve from the memory one or more results corresponding to and satisfying the query by perform 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 the at least some of the operations involve the plurality of input ciphertexts; and
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;
where the second computer system is further configured to send the one or more results of the evaluation of the circuit to the requestor;
where the requestor is configured to receive the one or more results and to decrypt the one or more results to determine an answer to the query.
12. The apparatus of claim 11 , 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.
13. The apparatus of claim 11 , 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.
14. The apparatus of claim 11 , 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.
15. The apparatus of claim 11 , where the 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.
16. An apparatus, comprising:
means for transmitting by requestor a query to a computer system;
means for receiving at the computer system the query;
means for accessing, at the computer system and from a memory of the computer system, a plurality of input ciphertexts, where each of the plurality of ciphertexts comprises data encrypted in accordance with an 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 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 encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme;
means for retrieving, by the computer system and from the memory, one or more results corresponding to and satisfying the query by performing homomorphic operations using at least the plurality of ciphertexts at least using:
means for performing operations on the 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;
means for reducing a noise level of the ciphertext result by using the refresh function; and
means for 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;
means for sending by the computer system the one or more results of the evaluation of the circuit to the requestor; and
means for receiving by the requestor the one or more results and means for decrypting by the requestor the one or more results to determine an answer to the query.
17. The apparatus of claim 16 , 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.
18. The apparatus of claim 16 , 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.
19. The apparatus of claim 16 , 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.
20. The apparatus of claim 16 , where the 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.
21. A method, comprising:
transmitting by a requestor a query to a computer system;
receiving at the computer system the query;
accessing, at the computer system and from a memory of the computer system, a plurality of input ciphertexts, where each of the plurality of ciphertexts comprises data encrypted in accordance with an 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 enable slow growth of a magnitude of noise for a provided ciphertext while maintaining a modulus of the provided ciphertext constant without using the secret key, where the encryption scheme enables homomorphic operations to be performed on ciphertexts encoded and operated on in accordance with the encryption scheme;
retrieving, by the computer system and from the memory, one or more results corresponding to and satisfying the query by 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 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;
sending by the computer system the one or more results of the evaluation of the circuit to the requestor; and
receiving by the requestor the one or more results and decrypting by the requestor the one or more results to determine an answer to the query.
22. The method of claim 21 , where the modulus of the provided ciphertext is maintained at a value of 1.
23. The method of claim 21 , where the magnitude of noise for the provided ciphertext is represented as a fractional part of coefficients for the ciphertext.
24. The method of claim 21 , 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.
25. The method of claim 21 , where the 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.