Secure computation of private values

• US 7,860,244 B2
• Filed: 12/18/2006
• Issued: 12/28/2010
• Est. Priority Date: 12/18/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Kerschbaum, Florian
• Primary Examiner(s): Gergiso; Techane J
• Application Number:
  US11/641,265
• Publication Number:
  US 20080144832A1
• Time in Patent Office: 1,471 Days
• Field of Search: 380/30, 380/277
• US Class Current: 380/30
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/30 Public key, i.e. encryption algorithm being computationally infeasible to invert or user's encryption keys not requiring secrecy

Abstract

An embodiment may include a system having a communication unit and a processing unit. The communication unit may be configured to receive an encrypted private value of a party, the encrypted private value being generated from a private value with a public-key encryption system and a public key, to send an encrypted blinded result to the party, and to receive a blinded result generated from the encrypted blinded result. The processing unit may be configured to compute a result of a function, the function having as input the private value, to blind the result of the function to generate the encrypted blinded result, and to compute the result by unblinding the blinded result.

Claims

1. A system comprising:

a hardware-based processing unit to

encrypt a private value of a party with a public-key encryption system and a public key to generate an encrypted private value and

decrypt an encrypted blinded result with the public-key encryption system and a private key to generate a blinded result; and

a communication unit to

send the encrypted private value to a further party,

receive the encrypted blinded result of a function, the function having as input the private value, and

send the blinded result to the further party, a first private value is a numerical value and the function is a summation function that adds the private value to private values of further parties, a second private value indicating whether the party contributes to a result of the summation function and the function is a counting function that counts contributions from the party and the further parties to generate a total number of contributing parties, the communication unit is further to receive an average value generated from the result of the summation function and a result of the counting function, and a third private value is a square of a difference between the numerical value and the average value and the function is the summation function.

2. The system of claim 1, comprising:

the processing unit to

compute a check value using an identifier of the party and the blinded result,

encrypt the check value with the public-key encryption system and the public key to generate an encrypted check value,

decrypt an encrypted sum of check values of the party and the further parties to generate a sum of check values, and

compare the sum of check values to a result of adding the check value to further check values of further parties, each one of the further check values computed from the blinded result and an identifier of the further parties; and

the communication unit to

receive the encrypted blinded result of the function, the function having as further input private values of the further parties,

send the encrypted check value to the further party, and

receive the encrypted sum of check values.

3. The system of claim 2, the processing unit further to compute the check value and each one of the further check values using a hash function having as input a sum of a random variable, the identifier of a party of the further parties, and the blinded result.

4. The system of claim 1, wherein the public-key encryption system is homomorphic and semantically secure.

5. The system of claim 1, wherein the blinded result is identical to a result multiplied by a random variable.

6. The system of claim 1, wherein the private value indicates if the party contributes to a result and the function is a counting function that counts contributions from the party and further parties to generate a total number of contributing parties.

7. A system comprising:

a communication unit to

receive an encrypted private value of a party, the encrypted private value being generated from a private value with a public-key encryption system and a public key, send an encrypted blinded result to the party, and receive a blinded result generated from the encrypted blinded result; and

a hardware-based processing unit to

compute a result of a function, the function having as input the private value,

blind the result of the function to generate the encrypted blinded result, and

compute the result by unblinding the blinded result, a first private value is a numerical value and the function is a summation function that adds the private value to private values of further parties, a second private value indicating whether the party contributes to a result of the summation function and the function is a counting function that counts contributions from the party and the further parties to generate a total number of contributing parties, the processing unit is further to compute an average value generated from the result of the summation function and a result of the counting function and the communication unit is further to send the average value to the party, and a third private value is a square of a difference between the numerical value and the average value and the function is the summation function.

8. The system of claim 7, comprising:

the processing unit to

compute the result of the function, the function having as further input private values of further parties and

add a check value to check values of the further parties to generate an encrypted sum of check values of the party and the further parties; and

the communication unit to

receive an encrypted check value generated from the check value with a public-key encryption system and a public key and

send the encrypted sum of check values to the party.

9. The system of claim 7, wherein the public-key encryption system is homomorphic and semantically secure.

10. The system of claim 7, wherein the processing unit is to blind the result of the function by multiplying the result by a random variable.

11. The system of claim 7, wherein the private value indicates if the party contributes to a further result and the function is a counting function that counts contributions from the party and further parties to generate a total number of contributing parties.

12. A method comprising:

encrypting, using a hardware-based processing unit of a first device, a private value of a party with a public-key encryption system and a public key to generate an encrypted private value;

sending the encrypted private value to a further party at a second device;

receiving an encrypted blinded result of a function, the function having as input the private value;

decrypting, the hardware-based processing unit, the encrypted blinded result with the public-key encryption system and a private key to generate a blinded result; and

sending the blinded result to the further party, wherein in a first executing operation the private value is a numerical value and the function is a summation function that adds the private value to private values of further parties;

in a second executing operation the private value indicates whether the party contributes to a result of the summation function and the function is a counting function that counts contributions from the party and the further parties to generate a total number of contributing parties;

receiving an average value generated from the result of the summation function and a result of the counting function; and

in a third executing operation the private value is a square of a difference between the numerical value and the average value and the function is the summation function.

13. The method of claim 12, comprising:

receiving the encrypted blinded result of the function, the function having as further input private values of further parties;

computing a check value using an identifier of the party and the blinded result;

encrypting the check value with the public-key encryption system and the public key to generate

an encrypted check value;

sending the encrypted check value to the further party;

receiving an encrypted sum of check values of the party and the further parties;

decrypting the encrypted sum of check values to generate a sum of check values; and

comparing the sum of check values to a result of adding the check value to further check values

of the further parties, each one of the further check values computed from the blinded result and an identifier of the further parties.

14. The method of claim 13, computing the check value and each one of the further check values using a hash function having as input a sum of a random variable, the identifier of a party of the further parties, and the blinded result.

15. The method of claim 12, wherein the public-key encryption system is homomorphic and semantically secure.

16. The method of claim 12, wherein the blinded result is identical to a result multiplied by a random variable.

17. The method of claim 12, wherein the private value indicates if the party contributes to a result and the function is a counting function that counts contributions from the party and further parties to generate a total number of contributing parties.

18. A method comprising:

receiving an encrypted private value of a party at a device, the encrypted private value generated from a private value with a public-key encryption system and a public key;

computing a result of a function, the function having as input the private value;

blinding the result of the function to generate an encrypted blinded result;

sending the encrypted blinded result to the party;

receiving a blinded result generated from the encrypted blinded result; and

computing, a hardware-based processing unit, the result of the function by unblinding the blinded result, wherein in a first executing operation the private value is a numerical value and the function is a summation function that adds the private value to private values of further parties;

in a second executing operation the private value indicates whether the party contributes to a result of the summation function and the function is a counting function that counts contributions from the party and the further parties to generate a total number of contributing parties;

computing an average value generated from the result of the summation function and a result of the counting function;

sending the average value to the party; and

in a third executing operation the private value is a square of a difference between the numerical value and the average value and the function is the summation function.

19. The method of claim 18, comprising:

computing the result of the function, the function having as further input private values of further parties;

receiving an encrypted check value generated from a check value with a public-key encryption system and a public key;

adding the check value to check values of the further parties to generate an encrypted sum of

check values of the party and the further parties; and

sending the encrypted sum of check values to the party.

20. The method of claim 18, wherein the public-key encryption system is homomorphic and semantically secure.

21. The method of claim 18, wherein blinding the result comprises multiplying the result by a random variable.

22. The method of claim 18, wherein the private value indicates if the party contributes to a result and the function is a counting function that counts contributions from the party and further parties to generate a total number of contributing parties.

23. A participant system comprising:

means for encrypting a private value of a party with a public-key encryption system and a public key to generate an encrypted private value and for decrypting an encrypted blinded result with the public-key encryption system and a private key to generate a blinded result; and

means for sending the encrypted private value to a further party, for receiving the encrypted blinded result of a function, the function having as input the private value, and for sending the blinded result to the further party, a first private value is a numerical value and the function is a summation function that adds the private value to private values of further parties, a second private value indicating whether the party contributes to a result of the summation function and the function is a counting function that counts contributions from the party and the further parties to generate a total number of contributing parties, the communication unit is further to receive an average value generated from the result of the summation function and a result of the counting function, and a third private value is a square of a difference between the numerical value and the average value and the function is the summation function.

24. A platform provider system comprising:

means for receiving an encrypted private value of a party, the encrypted private value generated from a private value with a public-key encryption system and a public key, for sending an encrypted blinded result to the party, and for receiving a blinded result generated from the encrypted blinded result; and

means for computing a result of a function, the function having as input the private value,

for blinding the result of the function to generate the encrypted blinded result, and for computing the result by unblinding the blinded result, a first private value is a numerical value and the function is a summation function that adds the private value to private values of further parties, a second private value indicating whether the party contributes to a result of the summation function and the function is a counting function that counts contributions from the party and the further parties to generate a total number of contributing parties, the communication unit is further to receive an average value generated from the result of the summation function and a result of the counting function, and a third private value is a square of a difference between the numerical value and the average value and the function is the summation function.

25. A non-transitory computer readable medium storing instructions, which when executed by hardware-based processing unit, performs a method comprising:

encrypting, using the hardware-based processing unit of a first device a private value of a party with a public-key encryption system and a public key to generate an encrypted private value;

sending the encrypted private value to a further party at a second device;

receiving an encrypted blinded result of a function, the function having as input the private value;

decrypting, using the hardware-based processing unit, the encrypted blinded result with the public-key encryption system and a private key to generate a blinded result; and

sending the blinded result to the further party, wherein in a first executing operation the private value is a numerical value and the function is a summation function that adds the private value to private values of further parties;

in a second executing operation the private value indicates whether the party contributes to a result of the summation function and the function is a counting function that counts contributions from the party and the further parties to generate a total number of contributing parties;

receiving an average value generated from the result of the summation function and a result of the counting function; and

in a third executing operation the private value is a square of a difference between the numerical value and the average value and the function is the summation function.

26. A non-transitory computer readable medium storing instructions, which when executed by a hardware-based processing unit, performs a method comprising:

receiving an encrypted private value of a party at a device, the encrypted private value generated from a

private value with a public-key encryption system and a public key;

computing a result of a function, the function having as input the private value;

blinding the result of the function to generate an encrypted blinded result;

sending the encrypted blinded result to the party;

receiving a blinded result generated from the encrypted blinded result; and

computing, using the hardware-based processing unit, the result of the function by unblinding the blinded result, wherein in a first executing

operation the private value is a numerical value and the function is a summation function that adds the private value to private values of further parties;

in a second executing operation the private value indicates whether the party contributes to a result of the summation function and the function is a counting function that counts contributions from the party and the further parties to generate a total number of contributing parties;

computing an average value generated from the result of the summation function and a result of the counting function;

sending the average value to the party; and

in a third executing operation the private value is a square of a difference between the numerical value and the average value and the function is the summation function.