Secure computation of private values

• US 20080144832A1
• Filed: 12/18/2006
• Published: 06/19/2008
• Est. Priority Date: 12/18/2006
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Kerschbaum, Florian
• Granted Patent: US 7,860,244 B2
• Time in Patent Office: Days
• US Class Current: 380/277
• 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 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.

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 function is a summation function that adds the private value to private values of further parties.

7. 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.

8. The system of claim 1, wherein 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, wherein a second private value indicates if 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, wherein 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 wherein 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.

9. 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 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.

10. The system of claim 9, 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.

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

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

13. The system of claim 9, wherein the function is a summation function that adds the private value to private values of further parties.

14. The system of claim 9, 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.

15. The system of claim 9, wherein 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, wherein a second private value indicates if 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, wherein 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 wherein the communication unit is further to send the average value to the party, and wherein 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.

16. A method comprising:

encrypting 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;

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

decrypting 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.

17. The method of claim 16, 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.

18. The method of claim 17, 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.

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

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

21. The method of claim 16, wherein the function is a summation function that adds the private value to private values of further parties.

22. The method of claim 16, 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. The method of claim 16, executing operations of claim 16, wherein 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;

executing operations of claim 16, wherein the private value indicates if the party contributes to a result of the summation function and wherein 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

executing operations of claim 16, wherein the 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 method comprising:

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;

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 the result of the function by unblinding the blinded result.

25. The method of claim 24, 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.

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

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

28. The method of claim 24, wherein the function is a summation function that adds the private value to private values of further parties.

29. The method of claim 24, 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.

30. The method of claim 24, executing operations of claim 24, wherein 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;

executing operations of claim 24, wherein the private value indicates if the party contributes to a result of the summation function and wherein 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

executing operations of claim 24, wherein the private value is a square of a difference between the numerical value and the average value and the function is the summation function.

31. A computer program product having instructions that are executable by a computer system, the computer program product comprising instructions of:

a processing module 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 to decrypt an encrypted blinded result with the public-key encryption system and a private key to generate a blinded result; and

a communication module to send the encrypted private value to a further party, to receive the encrypted blinded result of a function, the function having as input the private value, and to send the blinded result to the further party.

32. A computer program product having instructions that are executable by a computer system, the computer program product comprising instructions of:

a communication module to receive 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, to send an encrypted blinded result to the party, and to receive a blinded result generated from the encrypted blinded result; and

a processing module 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.

33. A participant system comprising:

first 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

second 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.

34. A platform provider system comprising:

first 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

second 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.