PRIVATE AND DISTRIBUTED COMPUTATION OF PROBABILITY DENSITY FUNCTIONS

• US 20150372808A1
• Filed: 06/18/2014
• Published: 12/24/2015
• Est. Priority Date: 06/18/2014
• Status: Abandoned Application

• Current Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Original Assignee: Palo Alto Research Center, Inc. (Xerox Holdings Corp.)
• Inventors: Bilogrevic, Igor, Freudiger, Julien F., De Cristofaro, Emiliano, Uzun, Ersin
• Application Number:
  US14/308,639
• Publication Number:
  US 20150372808A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06N 7/01 Probabilistic graphical models, e.g. probabilistic networks
• CPC Class Codes: H04L 2209/42 Anonymization, e.g. involving pseudonyms
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes

Abstract

One embodiment of the present invention provides a system for privacy-preserving aggregation of encrypted data. During operation, the system distributes secret keys to a plurality of devices. The system receives at least a pair of encrypted vectors from each device of a subset of the plurality of devices. One of the encrypted vectors is associated with a set of numerical values and the other encrypted vector is associated with corresponding square values of the set of numerical values. Each pair of encrypted vectors is encrypted using a respective secret key distributed to a device of the plurality of devices. The system then computes, for each pair of encrypted vector elements associated with a numerical value and a square of the numerical value, a mean and variance of a probability density function. The system then generates a plurality of probability density functions based on the computed mean and variance values.

Claims

1. A computer-executable method for privacy-preserving aggregation of encrypted data, comprising:

distributing secret keys to a plurality of devices;

receiving at least a pair of encrypted vectors from each device of a subset of the plurality of devices, wherein one of the encrypted vectors is associated with a set of numerical values and the other encrypted vector is associated with corresponding square values of the set of numerical values, each pair of encrypted vectors encrypted using a respective secret key distributed to a device of the plurality of devices;

computing, for each pair of encrypted vector elements associated with a numerical value and a square of the numerical value, a mean and variance of a probability density function; and

generating a plurality of probability density functions based on the computed mean and variance values.

2. The method of claim 1, wherein a sum of the respective secret keys distributed to each of the plurality of devices plus a secret key of an aggregator is equal to zero.

3. The method of claim 1, wherein generating the plurality of probability density functions comprises generating one or more probability density functions of Gaussian distributions.

4. The method of claim 1, wherein the encrypted vectors are received from users associated with the devices in exchange for a benefit of economic value to the users as part of a monetizing and/or advertising program.

5. The method of claim 1, wherein computing the mean and variance further comprises computing intermediate values {V_j, W_j} by computing the expressions:

V_j=H(t)^s0Π

_i=1^Nc_i,j

W_j=H(t)^s0Π

_i=1^Nb_i,j

such that b_i,j and c_i,j represent the encrypted data of each user i for an attribute j in a group of N users, s₀ represents the secret key for an aggregator, and H(t) represents a hash function at time t.

6. The method of claim 5, wherein computing the mean {circumflex over (μ

)}_j and the variance {circumflex over (σ

)}_j² associated with an attribute j comprises computing the expressions;

7. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for privacy-preserving aggregation of encrypted data, the method comprising:

distributing secret keys to a plurality of devices;

receiving at least a pair of encrypted vectors from each device of a subset of the plurality of devices, wherein one of the encrypted vectors is associated with a set of numerical values and the other encrypted vector is associated with corresponding square values of the set of numerical values, each pair of encrypted vectors encrypted using a respective secret key distributed to a device of the plurality of devices;

computing, for each pair of encrypted vector elements associated with a numerical value and a square of the numerical value, a mean and variance of a probability density function; and

generating a plurality of probability density functions based on the computed mean and variance values.

8. The computer-readable storage medium of claim 7, wherein a sum of the respective secret keys distributed to each of the plurality of devices plus a secret key of an aggregator is equal to zero.

9. The computer-readable storage medium of claim 7, wherein generating the plurality of probability density functions comprises generating one or more probability density functions of Gaussian distributions.

10. The computer-readable storage medium of claim 7, wherein the encrypted vectors are received from users associated with the devices in exchange for a benefit of economic value to the users as part of a monetizing and/or advertising program.

11. The computer-readable storage medium of claim 7, wherein computing the mean and variance further comprises computing intermediate values {V_j, W_j} by computing the expressions:

V_j=H(t)^s0Π

_i=1^Nc_i,j

W_j=H(t)^s0Π

_i=1^Nb_i,j

such that b_i,j and c_i,j represent the encrypted data of each user i for an attribute j in a group of N users, s₀ represents the secret key for an aggregator, and H(t) represents a hash function at time t.

12. The computer-readable storage medium of claim 7, wherein computing the mean {circumflex over (μ

)}_j and the variance {circumflex over (σ

)}_j² associated with an attribute j comprises computing the expressions;

13. A computing system for privacy-preserving aggregation of encrypted data, the system comprising:

one or more processors,

a computer-readable medium coupled to the one or more processors having instructions stored thereon that, when executed by the one or more processors, cause the one or more processors to perform operations comprising;

distributing secret keys to a plurality of devices;

receiving at least a pair of encrypted vectors from each device of a subset of the plurality of devices, wherein one of the encrypted vectors is associated with a set of numerical values and the other encrypted vector is associated with corresponding square values of the set of numerical values, each pair of encrypted vectors encrypted using a respective secret key distributed to a device of the plurality of devices;

computing, for each pair of encrypted vector elements associated with a numerical value and a square of the numerical value, a mean and variance of a probability density function; and

generating a plurality of probability density functions based on the computed mean and variance values.

14. The computing system of claim 13, wherein a sum of the respective secret keys distributed to each of the plurality of devices plus a secret key of an aggregator is equal to zero.

15. The computing system of claim 13, wherein generating the plurality of probability density functions comprises generating one or more probability density functions of Gaussian distributions.

16. The computing system of claim 13, wherein the encrypted vectors are received from users associated with the devices in exchange for a benefit of economic value to the users as part of a monetizing and/or advertising program.

17. The computing system claim 13, wherein computing the mean and variance further comprises computing intermediate values {V_j, W_j} by computing the expressions:

V_j=H(t)^s0Π

_i=1^Nc_i,j

W_j=H(t)^s0Π

_i=1^Nb_i,j

such that b_i,j and c_i,j represent the encrypted data of each user i for an attribute j in a group of N users, s₀ represents the secret key for an aggregator, and H(t) represents a hash function at time t.

18. The computing system of claim 13, wherein computing the mean {circumflex over (μ

)}_j and the variance {circumflex over (σ

)}_j² associated with an attribute j comprises computing the expressions;