Methods, systems, and computer program products for performing homomorphic encryption and decryption on individual operations

• US 8,681,973 B2
• Filed: 09/15/2010
• Issued: 03/25/2014
• Est. Priority Date: 09/15/2010
• Status: Expired due to Fees

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Inventors: Weinman, Joseph
• Primary Examiner(s): Louie, Oscar
• Assistant Examiner(s): JENKINS, BENJAMIN A
• Application Number:
  US12/882,753
• Publication Number:
  US 20120066510A1
• Time in Patent Office: 1,287 Days
• Field of Search: 713/189, 380/28
• US Class Current: 380/28
• CPC Class Codes: H04L 9/008 involving homomorphic encryption

Abstract

A method of processing data includes receiving a request for an operand from a second processor at a first processor, encrypting the operand that has been requested using the first processor responsive to receiving the request for the operand, sending the operand that has been encrypted from the first processor to the second processor, receiving a result from the second processor at the first processor, the result generated from a single homomorphic operation being performed using the operand sent to the second processor, decrypting the result received from the second processor at the first processor, and receiving a request for the result that has been decrypted from the second processor at the first processor.

Claims

1. A method of processing data, comprising:

receiving a request for an operand from a second processor at a first processor;

randomly generating a non-zero integer;

determining prime factors of the operand;

randomly selecting a divisor of the prime factors of the operand;

encrypting the operand that has been requested using the first processor responsive to receiving the request for the operand;

sending the operand that has been encrypted from the first processor to the second processor;

receiving a result from the second processor at the first processor, the result generated from a single homomorphic operation being performed using the operand sent to the second processor;

decrypting the result received from the second processor at the first processor;

storing the result that has been decrypted in a data store; and

receiving a request for the result that has been decrypted from the second processor at the first processor;

wherein encrypting the operand comprises encrypting the operand using a pad that comprises a fraction whose numerator is the non-zero integer and whose denominator is the divisor of the prime factors of the operand.

2. The method of claim 1, wherein the result is a first result and the single homomorphic operation is a single first homomorphic operation, the method further comprising:

encrypting the first result that has been requested using the first processor responsive to receiving the request for the first result;

sending the first result that has been encrypted from the first processor to the second processor;

receiving a second result from the second processor at the first processor, the second result generated from a single second homomorphic operation being performed using the first result sent to the second processor; and

decrypting the second result received from the second processor at the first processor.

3. The method of claim 1, wherein the first processor and second processor are coupled via an untrusted communication network.

4. The method of claim 3, wherein the first processor and the second processor are separate virtual machines that execute on a common hardware platform.

5. The method of claim 1, wherein the first processor and the second processor are in a same integrated circuit device.

6. The method of claim 1, wherein the pad is a multiplicative encryption pad, the method further comprising:

generating an additive encryption pad based on the operand and the operand that has been encrypted.

7. The method of claim 6, wherein decrypting the result comprises:

selecting one of the multiplicative encryption pad and the additive encryption pad based on the single homomorphic operation; and

using one of the selected multiplicative encryption pad and additive encryption pad to decrypt the result.

8. The method of claim 7, wherein the single homomorphic operation is an addition operation and wherein selecting one of the multiplicative encryption pad and the additive encryption pad comprises selecting the additive encryption pad.

9. The method of claim 7, wherein the single homomorphic operation is a multiplication operation and wherein selecting one of the multiplicative encryption pad and the additive encryption pad comprises selecting the multiplicative encryption pad.

10. The method of claim 7, wherein the single homomorphic operation is a copy operation and wherein selecting one of the multiplicative encryption pad and the additive encryption pad comprises selecting the additive encryption pad.

11. The method of claim 7, wherein the single homomorphic operation is a negation operation and wherein selecting one of the multiplicative encryption pad and the additive encryption pad comprises selecting the additive encryption pad.

12. The method of claim 7, wherein the single homomorphic operation is an inversion operation and wherein selecting one of the multiplicative encryption pad and the additive encryption pad comprises selecting the multiplicative encryption pad.

13. A data processing system, comprising:

a memory comprising computer readable program code; and

a first processor that is coupled to the memory and is to execute the computer readable program code so as to cause the data processing system to perform operations comprising;

receiving a request for an operand from a second processor at the first processor;

randomly generating a non-zero integer;

determining prime factors of the operand;

randomly selecting a divisor of the prime factors of the operand;

encrypting the operand that has been requested using the first processor responsive to receiving the request for the operand;

sending the operand that has been encrypted from the first processor to the second processor;

receiving a result from the second processor at the first processor, the result generated from a single homomorphic operation being performed using the operand sent to the second processor;

decrypting the result received from the second processor at the first processor;

storing the result that has been decrypted in a data store; and

receiving a request for the result that has been decrypted from the second processor at the first processor;

wherein encrypting the operand comprises encrypting the operand using a pad that comprises a fraction whose numerator is the non-zero integer and whose denominator is the divisor of the prime factors of the operand.

14. The data processing system of claim 13, wherein the first processor and second processor are coupled via an untrusted communication network,

15. The data processing system of claim 13, wherein the first processor and the second processor are in a same integrated circuit device.

16. The data processing system of claim 15, wherein the first processor and the second processor are separate virtual machines that execute on a common hardware platform.

17. An article of manufacture, comprising:

a non-transitory computer readable storage medium having computer readable program code embodied therein, the computer readable program code when executed by a first processor causing the first processor to perform operations comprising;

receiving a request for an operand from a second processor at a first processor;

randomly generating a non-zero integer;

determining prime factors of the operand;

randomly selecting a divisor of the prime factors of the operand;

encrypting the operand that has been requested using the first processor responsive to receiving the request for the operand;

sending the operand that has been encrypted from the first processor to the second processor;

receiving a result from the second processor at the first processor, the result generated from a single homomorphic operation being performed using the operand sent to the second processor;

decrypting the result received from the second processor at the first processor;

storing the result that has been decrypted in a data store; and

receiving a request for the result that has been decrypted from the second processor at the first processor;

wherein encrypting the operand comprises encrypting the operand using a pad that comprises a fraction whose numerator is the non-zero integer and whose denominator is the divisor of the prime factors of the operand.

18. The article of manufacture of claim 17, wherein the first processor and second processor are coupled via an untrusted communication network.

19. The article of manufacture of claim 17, wherein the first processor and the second processor are in a same integrated circuit device.

20. The article of manufacture of claim 19, wherein the first processor and the second processor are separate virtual machines that execute on a common hardware platform.