Interactive bootstrapping for approximate homomorphic encryption

1. A computer implemented method for distributing bootstrapping in homomorphic encryption schemes, the method comprising:

splitting, by a server, a decryption key into a plurality of n shares, where n is an integer;

transmitting, by the server, to each of a plurality of n computer processors:

(i) a ciphertext, wherein the ciphertext is encrypted using homomorphic encryption;

(ii) a unique share of the plurality of n shares of the decryption key; and

(iii) an indication of a publicly available encryption key;

receiving, by the server, from each of the plurality of n computer processors, n encrypted values,

wherein each of the n encrypted values is a re-encryption of a decryption of the ciphertext, the re-encryption performed by each of the plurality of n computer processors using the publicly available encryption key, and the decryption of the ciphertext performed by each of the plurality of n computer processors using the unique share of the plurality of n shares of the decryption key transmitted to each of the plurality of n computer processors; and

computing, by the server, a homomorphic sum of the n encrypted values to obtain an encryption of the sum of n decrypted values, such that a bootstrapping of the encryption is distributed,

wherein the ciphertext is decrypted by each of the plurality of n computer processors using the unique share of the plurality of n shares of the decryption key transmitted to the plurality of n computer processors, and a modulus, wherein the modulus is different for each of the plurality of n computer processors.

2. The method of claim 1 , wherein each of the plurality of n computer processors are located on the server.

3. The method of claim 1 , wherein each of the plurality of n computer processors are located on a same second server.

4. The method of claim 1 , wherein each of the plurality of n computer processors are located on a corresponding plurality of n different servers.

5. The method of claim 4 , wherein each of the plurality of n different servers are semi-honest servers.

6. The method of claim 1 , wherein the ciphertext is encrypted using the Cheon-Kim-Kim-Song (CKKS) approximate homomorphic encryption scheme.

7. The method of claim 1 , wherein the ciphertext comprises a pair of ring elements from a cyclotomic ring.

8. The method of claim 1 , wherein each of the n encryption values are independent of the decryption key.

9. The method of claim 1 , wherein the decryption of the ciphertext is rounded if an absolute value of the decryption of the ciphertext is greater than a predefined value.

10. The method of claim 1 , wherein the server transmits, to each of the plurality of n computer processors, a hash function, and

wherein the decryption of the ciphertext comprises the hash function.

11. A system for distributing bootstrapping in homomorphic encryption schemes, the system comprising:

a server; and

a plurality of n computer processors, where n is an integer,

wherein the server is configured to:

split a decryption key into a plurality of n shares;

transmit, to each of the plurality of n computer processors:

(i) a ciphertext, wherein the ciphertext is encrypted using homomorphic encryption;

(ii) a unique share of the plurality of n shares of the decryption key; and

(iii) an indication of a publicly available encryption key;

receive, from each of the plurality of n computer processors, n encrypted values,

wherein each of the n encrypted values is a re-encryption of a decryption of the ciphertext, the re-encryption performed by each of the plurality of n computer processors using the publicly available encryption key, and the decryption of the ciphertext performed by each of the plurality of n computer processors using the unique share of the plurality of n shares of the decryption key transmitted to each of the plurality of n computer processors; and

compute a homomorphic sum of the n encrypted values to obtain an encryption of the sum of n decrypted values, such that a bootstrapping of the encryption is distributed,

wherein the ciphertext is decrypted by each of the plurality of n computer processors using the unique share of the plurality of n shares of the decryption key transmitted to the plurality of n computer processors, and a modulus, wherein the modulus is different for each of the plurality of n computer processors.

12. The system of claim 11 , wherein each of the plurality of n computer processors are located on the server.

13. The system of claim 11 , wherein each of the plurality of n computer processors are located on a same second server.

14. The system of claim 11 , wherein each of the plurality of n computer processors are located on a corresponding plurality of n different servers.

15. The system of claim 11 , wherein each of the plurality of n computer processors are configured to round the decryption of the ciphertext if an absolute value of the decryption of the ciphertext is greater than a predefined value.

16. The system of claim 11 , wherein the server is configured to transmit, to each of the plurality of n computer processors, a hash function to be used in the decryption of the ciphertext.

17. A computer readable non-transitory storage medium storing instructions which when executed by at least one processor in a server cause the at least one server to:

split a decryption key into a plurality of n shares, where n is an integer;

transmit, to each of a plurality of n computer processors:

(i) a ciphertext, wherein the ciphertext is encrypted using homomorphic encryption;

(ii) a unique share of the plurality of n shares of the decryption key; and

(iii) an indication of a publicly available encryption key;

receive, from each of the plurality of n computer processors, n encrypted values,

wherein each of the n encrypted values is a re-encryption of a decryption of the ciphertext, the re-encryption performed by each of the plurality of n computer processors using the publicly available encryption key, and the decryption of the ciphertext performed by each of the plurality of n computer processors using the unique share of the plurality of n shares of the decryption key transmitted to each of the plurality of n computer processors; and

compute a homomorphic sum of the n encrypted values to obtain an encryption of the sum of n decrypted values, such that a bootstrapping of the encryption is distributed,

wherein the ciphertext is decrypted by each of the plurality of n computer processors using the unique share of the plurality of n shares of the decryption key transmitted to the plurality of n computer processors, and a modulus, wherein the modulus is different for each of the plurality of n computer processors.