Computation using somewhat homomorphic encryption

1. A device comprising:

a memory operative to store data used by a processor of a first device;

a network interface operative to communicate over a network with a second device; and

the processor configured to:

generate a Somewhat Homomorphic Encryption of a plurality of secret shares;

provide the Somewhat Homomorphic Encryption of the plurality of secret shares to the second device;

perform the following in a loop:

obtain a first result of a homomorphic exclusive-or operation performed by the second device on the Somewhat Homomorphic Encryption of the plurality of secret shares;

perform a Somewhat Homomorphic Decryption of the first result, yielding a second result;

perform a Somewhat Homomorphic Encryption of the second result yielding a third result;

transmit the third result to the second device; and

obtain a final Somewhat Homomorphically Encrypted result from the second device;

decrypt the final Somewhat Homomorphically Encrypted result in order to produce a final Somewhat Homomorphically Decrypted output; and

output the final Somewhat Homomorphically Decrypted output.

2. The device of claim 1 , wherein the processor is configured to publish the output.

3. The device of claim 1 , wherein the processor is configured to provide the output to the second device.

4. The device of claim 1 , wherein the processor is configured to keep the output as a secret.

5. The device of claim 1 , wherein the processor is configured to use a Somewhat Homomorphic Encryption scheme that includes a learning with errors Somewhat Homomorphic Encryption scheme.

6. The device of claim 1 , wherein the processor is configured to use a Somewhat Homomorphic Encryption scheme that includes a ring-learning with errors Somewhat Homomorphic Encryption scheme.

7. The device of claim 1 , wherein the processor is configured to reduce noise associated with the first result when the processor performs the Somewhat Homomorphic Encryption of the second result.

8. The device of claim 1 wherein noise in the first result is bounded by a multiplicative depth of a circuit associated with the plurality of secret shares.

9. A device comprising:

a memory operative to store data used by a processor of a first device;

a network interface operative to communicate over a network with a second device; and

the processor configured to:

obtain a Somewhat Homomorphic Encrypted first plurality of secret shares from the second device;

use a public key to generate a Somewhat Homomorphic Encrypted second plurality of secret shares;

perform a homomorphic exclusive-or operation on the first plurality of secret shares and the second plurality of secret shares yielding a first result;

perform the following in a loop:

perform a function on the first result yielding a second result;

mask the second result with random encrypted bits yielding a masked result;

provide the masked result to the second device;

obtain a re-encrypted output from the second device; and

perform a second homomorphic exclusive-or operation on the re-encrypted output yielding a third result;

perform a second function on the third result yielding a fourth result; and

provide the fourth result to the second device.

10. The device of claim 9 , wherein the processor is configured to obtain a final Somewhat Homomorphically Decrypted output from the second device.

11. The device of claim 9 , wherein the processor is configured to use a Somewhat Homomorphic Encryption scheme that includes a learning with errors Somewhat Homomorphic Encryption scheme.

12. The device of claim 9 , wherein the processor is configured to use a Somewhat Homomorphic Encryption scheme that includes a ring-learning with errors Somewhat Homomorphic Encryption scheme.

13. The device of claim 9 , wherein the re-encrypted output obtained from the second device is obtained after the second device has performed a noise reduction operation prior to re-encrypting the re-encrypted output.

14. The device of claim 9 , wherein the homomorphic exclusive-or operation adds noise to the first result, the noise being bounded by a multiplicative depth of a circuit associated with the plurality of secret shares.

15. The device of claim 9 , wherein the function performed on the first result is comprised of Boolean operations.

16. The device of claim 9 , wherein the processor is configured to perform a homomorphic exclusive-or operation on the second result in order to mask the result of the function.

17. The device of claim 9 , wherein the processor is configured to perform a second homomorphic exclusive-or operation in order to unmask encrypted bits comprised in the re-encrypted output.

18. A method comprising:

storing data in a memory, the data for use by a processor of a first device;

communicating over a network with a second device via a network interface; and

at a processor:

generating a Somewhat Homomorphic Encryption of a plurality of secret shares;

providing the Somewhat Homomorphic Encryption of the plurality of secret shares to the second device;

performing the following in a loop:

obtaining a first result of a homomorphic exclusive-or operation performed by the second device on the Somewhat Homomorphic Encryption of the plurality of secret shares;

performing a Somewhat Homomorphic Decryption of the first result, yielding a second result;

performing a Somewhat Homomorphic Encryption of the second result yielding a third result;

providing the third result to the second device; and

obtaining a final Somewhat Homomorphically Encrypted result from the second device;

decrypting the final Somewhat Homomorphically Encrypted result in order to produce a final Somewhat Homomorphically Decrypted output; and

outputting the final Somewhat Homomorphically Decrypted output.

19. The method of claim 18 , wherein one of:

the first device publishes the output;

the first device sends the output to the second device; and

the first device keeps the output as a secret.

20. The method of claim 18 , wherein a Somewhat Homomorphic Encryption scheme used by the first device comprises one of:

a learning with errors Somewhat Homomorphic Encryption scheme; and

a ring-learning with errors Somewhat Homomorphic Encryption scheme.