Privacy-preserving aggregation of Time-series data

• US 8,555,400 B2
• Filed: 02/04/2011
• Issued: 10/08/2013
• Est. Priority Date: 02/04/2011
• Status: Active Grant

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Shi, Runting, Chow, Richard, Chan, Tsz Hong Hubert
• Primary Examiner(s): Orgad, Edan
• Assistant Examiner(s): JACKSON, JENISE E
• Application Number:
  US13/021,538
• Publication Number:
  US 20120204026A1
• Time in Patent Office: 977 Days
• Field of Search: 726/26, 380/277, 713/171
• US Class Current: 726/26
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/46 Secure multiparty computation, e.g. millionaire problem
• CPC Class Codes: H04L 9/008 involving homomorphic encryption
• CPC Class Codes: H04L 9/0833 involving conference or group key network architectures or network communication protocols for key management in group communication in a packet data network H04L63/065
• CPC Class Codes: H04L 9/088 Usage controlling of secret information, e.g. techniques for restricting cryptographic keys to pre-authorized uses, different access levels, validity of crypto-period, different key- or password length, or different strong and weak cryptographic algorithms network architectures or network communication protocols for using time-dependent keys in a packet data network H04L63/068
• CPC Class Codes: H04L 9/3006 underlying computational problems or public-key parameters

Abstract

A private stream aggregation (PSA) system contributes a user'"'"'s data to a data aggregator without compromising the user'"'"'s privacy. The system can begin by determining a private key for a local user in a set of users, wherein the sum of the private keys associated with the set of users and the data aggregator is equal to zero. The system also selects a set of data values associated with the local user. Then, the system encrypts individual data values in the set based in part on the private key to produce a set of encrypted data values, thereby allowing the data aggregator to decrypt an aggregate value across the set of users without decrypting individual data values associated with the set of users, and without interacting with the set of users while decrypting the aggregate value. The system also sends the set of encrypted data values to the data aggregator.

Claims

1. A method for sharing sensitive data with a data aggregator, the method comprising:

determining a private key for a local user in a set of users, wherein the sum of the private keys associated with the set of users and the data aggregator is equal to zero;

selecting, at a client computer, a set of data values associated with the local user;

encrypting individual data values in the set based in part on the private key to produce a set of encrypted data values, thereby allowing the data aggregator to decrypt an aggregate value across the set of users without decrypting individual data values associated with the set of users, and without interacting with the set of users while decrypting the aggregate value; and

sending the set of encrypted data values to the data aggregator;

wherein the set of data values includes a time series, wherein the private key is determined prior to encrypting the individual data values in the time series, wherein the aggregate value includes a summation of the individual values associated with the set of users; and

wherein encrypting an individual data value x_i,t for a user i and time period t involves computing an expression;

c_i,t=g^xi,t·

H(t)^ski

wherein c_i,t is an encrypted value associated with user i and time period t, wherein g is a generator, wherein sk_i is a private key associated with user i, and wherein H(t) is a hash function.

2. The method of claim 1, wherein determining the private key for the local user comprises receiving the private key from a trusted source.

3. The method of claim 1, wherein determining the private key for the local user comprises using a secure multi-party protocol.

4. The method of claim 1, wherein encrypting the individual data values involves adding random values to at least a subset of the data values to produce a modified set of data values with random noise.

5. The method of claim 4, wherein the random values are chosen from a pre-determined distribution to minimize the total noise introduced to the aggregate value by the set of users to:

6. The method of claim 1, wherein encrypting the individual data values involves also encrypting higher moments of the individual data values, thereby allowing the data aggregator to determine a distribution for the data values across the set of users.

7. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for sharing sensitive data with a data aggregator, the method comprising:

determining a private key for a local user in a set of users, wherein the sum of the private keys associated with the set of users and the data aggregator is equal to zero;

selecting a set of data values associated with the local user;

encrypting individual data values in the set based in part on the private key to produce a set of encrypted data values, thereby allowing the data aggregator to decrypt an aggregate value across the set of users without decrypting individual data values associated with the set of users, and without interacting with the set of users while decrypting the aggregate value; and

sending the set of encrypted data values to the data aggregator;

wherein the set of data values includes a time series, wherein the private key is determined prior to encrypting the individual data values in the time series, and wherein the aggregate value includes a product of the individual values associated with the set of users; and

wherein encrypting an individual data value x_i,t for a user i and time period t involves computing an expression;

c_i,t=x_i,t·

H(t)^ski

wherein c_i,t is the encrypted value associated with user i and time period t, wherein sk_i is a private key associated with user i, and wherein H(t) is a hash function.

8. The computer-readable storage medium of claim 7, wherein determining the private key for the local user comprises receiving the private key from a trusted source.

9. The computer-readable storage medium of claim 7, wherein determining the private key for the local user comprises using a secure multi-party protocol.

10. The computer-readable storage medium of claim 7, wherein encrypting the individual data values involves adding random values to at least a subset of the data values to produce a modified set of data values with random noise.

15. The computer-readable storage medium of claim 7, wherein the random values are chosen from a pre-determined distribution to minimize the total noise introduced to the aggregate value by the set of users to:

16. The computer-readable storage medium of claim 10, wherein encrypting the individual data values involves also encrypting higher moments of the individual data values, thereby allowing the data aggregator to determine a distribution for the data values across the set of users.

11. An apparatus for sharing sensitive data with a data aggregator, the method comprising:

a setup mechanism configured to determine a private key for a local user in a set of users, wherein the sum of the private keys associated with the set of users and the data aggregator is equal to zero;

an encrypt mechanism configured to;

select a set of data values associated with the local user; and

encrypt individual data values in the set based in part on the private key to produce a set of encrypted data values, thereby allowing the data aggregator to decrypt an aggregate value across the set of users without decrypting individual data values associated with the set of users, and without interacting with the set of users while decrypting the aggregate value; and

a communication mechanism configured to send the set of encrypted data values to the data aggregator;

wherein the set of data values includes a time series, wherein the private key is determined prior to encrypting the individual data values in the time series, and wherein the aggregate value includes a summation of the individual values associated with the set of users; and

wherein while encrypting an individual data value x_i,t for a user i and time period t, the encrypt mechanism is further configured to compute an expression;

c_i,t=g^xi,t·

H(t)^ski

wherein c_i,t is an encrypted value associated with user i and time period t, wherein g is a generator, wherein sk_i is a private key associated with user i, and wherein H(t) is a hash function.

12. The apparatus of claim 11, wherein determining the private key for the local user comprises receiving the private key from a trusted source.

13. The apparatus of claim 11, wherein determining the private key for the local user comprises using a secure multi-party protocol.

14. The apparatus of claim 11, wherein encrypting the individual data values involves adding random values to at least a subset of the data values to produce a modified set of data values with random noise.

17. The apparatus of claim 11, wherein the random values are chosen from a pre-determined distribution to minimize the total noise introduced to the aggregate value by the set of users to:

18. The apparatus of claim 14, wherein while encrypting the individual data values, the encrypt mechanism is further configured to also encrypt higher moments of the individual data values, thereby allowing the data aggregator to determine a distribution for the data values across the set of users.