Fault-Tolerant Privacy-Preserving Statistics

• US 20130275743A1
• Filed: 04/12/2012
• Published: 10/17/2013
• Est. Priority Date: 04/12/2012
• Status: Active Grant

• Current Assignee: SAP SE
• Original Assignee: SAP AG (SAP SE)
• Inventors: Kerschbaum, Florian, Jawurek, Marek
• Granted Patent: US 8,880,867 B2
• Time in Patent Office: Days
• US Class Current: 713/150
• CPC Class Codes: H04L 9/008 involving homomorphic encryption

Abstract

Disclosed is a protocol for a fault-tolerant, private distributed aggregation model that allows a data consumer to calculate unbounded statistics (weighted sums) over homomorphically encrypted sensitive data items from data producers. The data consumer can choose to calculate over an arbitrary subset of all available data items, thus providing fault tolerance; i.e., failing data producers do not prevent the statistics calculation. A key-managing authority ensures differential privacy before responding to the data consumer'"'"'s decryption request for the homomorphically encrypted statistics result, thus preservation the data'"'"'s producer'"'"'s privacy. Security against malicious data consumers is provided along with aggregator obliviousness, differential privacy in a unidirectional communication model between data producers and data consumers.

Claims

1. A method in a first system for performing a computation that is representative of applying a function ƒ

on a plurality of plaintext data, the method comprising;

receiving a plurality of ciphertext data from a plurality of data producers, the ciphertext data being obtained respectively from the plaintext data using an encryption algorithm of a homomorphic cryptographic system;

producing a computed value from the ciphertext data using a function ƒ

_h that is derived from the function ƒ

using a relationship defined by the homomorphic cryptographic system;

sending the computed value to a second system separate from the first system; and

receiving from the second system an extracted value that is based on the computed value, the extracted value representative of a computed result produced by applying the function ƒ

on the plurality of plaintext data.

2. The method of claim 1 wherein the ciphertext data have a one-to-one correspondence with the data producers.

3. The method of claim 1 wherein the ciphertext data are encrypted using an encryption key that is common to each of the data producers, wherein the second system uses a decryption key to decrypt the computed value received from the first system.

4. The method of claim 3 wherein the encryption key is a public key portion of a public key/private key cryptographic system, wherein the decryption key is a private key portion of the public key/private key cryptographic system.

5. The method of claim 1 wherein the first system includes a blinding term among the plurality of ciphertext data when producing the computed value.

6. The method of claim 1 wherein the second system incorporates a random sample term in the extracted value.

7. The method of claim 1 wherein a plurality of computed values are produced from the ciphertext data, wherein each computed value is sent to a second system from among a plurality of second systems, wherein at least some of the second systems each returns a shared value, the method further comprising combining the received shared values to produce a result that represents a computed result produced by applying the function ƒ

on the plaintext data.

8. The method of claim 1 further comprising receiving from each data producer p_j an ordinal value P_j associated with the plaintext datum that is represented by the ciphertext datum sent by the data producer, and sending p_j and P_j received from each data producer to the second system, wherein the second system uses the received p_j and P_j data to determine whether the data used to generate the computed value in the first system have been used to generate a previous computed value.

9. A system comprising:

a central processing unit; and

a data storage device having stored thereon computer executable program code,

wherein when the central processing unit executes the computer executable program code, the central processing unit;

receives a plurality of ciphertext data from a plurality of data producers, the ciphertext data being obtained respectively from the plaintext data using an encryption algorithm of a homomorphic cryptographic system;

produces a computed value from the ciphertext data using a function ƒ

_h that is derived from the function ƒ

using a relationship defined by the homomorphic cryptographic system;

sends the computed value to a decryption system separate from the system; and

receives from the decryption system an extracted value that is based on the computed value, the extracted value representative of a computed result produced by applying the function f on the plurality of plaintext data.

10. The system of claim 9 wherein the ciphertext data are encrypted using an encryption key that is common to each of the data producers, wherein the decryption system uses a decryption key to decrypt the received computed value.

11. The system of claim 10 wherein the encryption key is a public key portion of a public key/private key cryptographic system, wherein the decryption key is a private key portion of the public key/private key cryptographic system.

12. The system of claim 9 wherein a blinding term is included among the plurality of ciphertext data when producing the computed value.

13. The system of claim 9 wherein the decryption system incorporates a random sample term in the extracted value.

14. The system of claim 9 wherein a plurality of computed values are produced from the ciphertext data, wherein each computed value is sent to an instance of a plurality of decryption system, wherein at least some of the instances of the decryption systems each returns a shared value, the method further comprising combining the received shared values to produce a combined result that represents a computed result produced by applying the function ƒ

on the plaintext data.

15. The system of claim 9 wherein when the central processing unit executes the computer executable program code, the central processing unit further receives from each data producer p_j an ordinal value P_j associated with the plaintext datum that is represented by the ciphertext datum sent by the data producer, and sends p_j and P_j received from each data producer to the decryption system, wherein the decryption system uses the received p_j and P_j data to determine whether the data used to generate the computed value in the first system have been used to generate a previous computed value.

16. A non-transitory computer readable storage medium having stored thereon computer executable program code, which when executed by a computer system causes the system to perform steps of:

receiving a plurality of ciphertext data from a plurality of data producers, the ciphertext data being obtained respectively from the plaintext data using an encryption algorithm of a homomorphic cryptographic system;

producing a computed value from the ciphertext data using a function ƒ

_h that is derived from the function ƒ

using a relationship defined by the homomorphic cryptographic system;

sending the computed value to a second system separate from the first system; and

receiving from the second system an extracted value that is based on the computed value, the extracted value representative of a computed result produced by applying the function ƒ

on the plurality of plaintext data.

17. The non-transitory computer readable storage medium of claim 16 wherein the ciphertext data are encrypted using an encryption key that is common to each of the data producers, wherein the second system uses a decryption key to decrypt the computed value received from the first system.

18. The non-transitory computer readable storage medium of claim 17 wherein the encryption key is a public key portion of a public key/private key cryptographic system, wherein the decryption key is a private key portion of the public key/private key cryptographic system.

19. The non-transitory computer readable storage medium of claim 16 wherein the first system includes a blinding term among the plurality of ciphertext data when producing the computed value.

20. The non-transitory computer readable storage medium of claim 16 wherein the second system incorporates a random sample term in the extracted value.