PRIVACY-SENSITIVE RANKING OF USER DATA

• US 20150371059A1
• 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,629
• Publication Number:
  US 20150371059A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: H04L 9/08 Key distribution or management, e.g. generation, sharing or updating, of cryptographic keys or passwords network architectures or network communication protocols for supporting key management in a packet data network H04L63/06
• CPC Class Codes: H04L 9/0819 Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely transfers it to the other(s) network architectures or network communication protocols for key distribution in a packet data network H04L63/062
• 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-sensitive ranking of aggregated data. During operation, the system distributes secret keys to a plurality of devices. The system then generates a plurality of probability density functions in a privacy-preserving way using encrypted data received from a subset of the plurality of devices. The encrypted data is data that has been encrypted with one or more of the secret keys by the subset of devices. The system then generates a plurality of probability mass functions, each probability mass function associated with a corresponding probability density function. Subsequently, the system computes a plurality of distance values, each respective distance value being a measure of distance from a probability mass function to a second distribution. The system then ranks the probability mass functions and/or associated attributes according to their respective distance from the second distribution.

Claims

1. A computer-executable method for privacy-sensitive ranking of aggregated data, comprising:

distributing secret keys to a plurality of devices;

generating a plurality of probability density functions in a privacy-preserving way using encrypted data received from a subset of the plurality of devices, wherein the encrypted data is encrypted with one or more of the secret keys;

generating a plurality of probability mass functions, each probability mass function associated with a corresponding probability density function;

computing a plurality of distance values, each respective distance value being a measure of distance from a probability mass function to a second distribution; and

ranking the probability mass functions and/or associated attributes according to their respective distance from the second distribution.

2. The method of claim 1, wherein computing the plurality of distance values comprises computing a Jensen-Shannon divergence for each of the distance values.

3. The method of claim 1, further comprising:

receiving a minimum distance value λ

_i,j from each of the plurality of devices for an attribute j;

comparing each λ

_i,j to a respective distance value d_j, to determine whether a user i who contributed minimum distance value λ

_i,j is willing to share data for attribute j;

computing a ratio γ

_j=S_j/N where S_j=|{iε

U s·

t·

d_j≦

1−

λ

_i,j}| is the number of users that are willing to share attribute j out of a total of N users; and

determining that the ratio γ

_j is greater than a predetermined threshold; and

sharing a probability mass function and/or a probability density function for attribute j with a customer.

4. The method of claim 1, wherein ranking the probability mass functions and associated attributes comprises ranking distances d_j associated with attributes such that d_ρ

1≦

d<sub>ρ

2</sub>≦

. . . ≦

d<sub>ρ

K</sub>, where ρ

₁=arg min_j d_j and ρ

_z=arg min<sub>j≠

{ρ

k}k=1z−

1</sub>(d_j) for 2≦

z≦

K

such that j represents an attribute out of a total number of K attributes.

5. The method of claim 1, further comprising sending a distance value d_j to a user for attribute j, and receiving from the user a request for an increase in monetary retribution in exchange for selling aggregate data associated with attribute j to a customer.

6. The method of claim 1, further comprising re-computing a probability density function for attribute j using only data from those users that have indicated a willingness to share their attribute j data, and sharing the re-computed probability density function with a customer.

7. The method of claim 1, wherein generating the plurality of probability density functions comprises:

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 respective 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 the plurality of probability density functions based on the computed mean and variance values.

8. A computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for privacy-sensitive ranking of aggregated data, the method comprising:

distributing secret keys to a plurality of devices;

generating a plurality of probability density functions in a privacy-preserving way using encrypted data received from a subset of the plurality of devices, wherein the encrypted data is encrypted with one or more of the secret keys;

generating a plurality of probability mass functions, each probability mass function associated with a corresponding probability density function;

computing a plurality of distance values, each respective distance value being a measure of distance from a probability mass function to a second distribution; and

ranking the probability mass functions and/or associated attributes according to their respective distance from the second distribution.

9. The computer-readable storage medium of claim 8, wherein computing the plurality of distance values comprises computing a Jensen-Shannon divergence for each of the distance values.

10. The computer-readable storage medium of claim 8, wherein the method further comprises:

receiving a minimum distance value λ

_i,j from each of the plurality of devices for an attribute j;

comparing each λ

_i,j to a respective distance value d_j, to determine whether a user i who contributed minimum distance value λ

_i,j is willing to share data for attribute j;

computing a ratio γ

_j=S_j/N where S_j=|{iε

U s·

t·

d_j≦

1−

λ

_i,j}| is the number of users that are willing to share attribute j out of a total of N users; and

determining that the ratio γ

_j is greater than a predetermined threshold; and

sharing a probability mass function and/or a probability density function for attribute j with a customer.

11. The computer-readable storage medium of claim 8, wherein ranking the probability mass functions and associated attributes comprises ranking distances d_j associated with attributes such that d_ρ

1≦

d<sub>ρ

2</sub>≦

. . . ≦

d<sub>ρ

K</sub>, where ρ

₁=arg min_j d_j and ρ

_z=arg min<sub>j≠

{ρ

k}k=1z−

1</sub>(d_j) for 2≦

z≦

K

such that j represents an attribute out of a total number of K attributes.

12. The computer-readable storage medium of claim 8, wherein the method further comprises:

sending a distance value d_j to a user for attribute j, and receiving from the user a request for an increase in monetary retribution in exchange for selling aggregate data associated with attribute j to a customer.

13. The computer-readable storage medium of claim 8, wherein the method further comprises re-computing a probability density function for attribute j using only data from those users that have indicated a willingness to share their attribute j data, and sharing the re-computed probability density function with a customer.

14. The computer-readable storage medium of claim 8, wherein generating the plurality of probability density functions comprises:

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 respective 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 the plurality of probability density functions based on the computed mean and variance values.

15. A computing system for privacy-sensitive ranking of aggregated 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;

generating a plurality of probability density functions in a privacy-preserving way using encrypted data received from a subset of the plurality of devices, wherein the encrypted data is encrypted with one or more of the secret keys;

generating a plurality of probability mass functions, each probability mass function associated with a corresponding probability density function;

computing a plurality of distance values, each respective distance value being a measure of distance from a probability mass function to a second distribution; and

ranking the probability mass functions and/or associated attributes according to their respective distance from the second distribution.

16. The computing system of claim 15, wherein computing the plurality of distance values comprises computing a Jensen-Shannon divergence for each of the distance values.

17. The computing system of claim 15, wherein the operations further comprise:

receiving a minimum distance value λ

_i,j from each of the plurality of devices for an attribute j;

comparing each λ

_i,j to a respective distance value d_j, to determine whether a user i who contributed minimum distance value λ

_i,j is willing to share data for attribute j;

computing a ratio γ

_j=S_j/N where S_j=|{iε

U s·

t·

d_j≦

1−

λ

_i,j}| is the number of users that are willing to share attribute j out of a total of N users; and

determining that the ratio γ

_j is greater than a predetermined threshold; and

sharing a probability mass function and/or a probability density function for attribute j with a customer.

18. The computing system of claim 15, wherein ranking the probability mass functions and associated attributes comprises ranking distances d_j associated with attributes such that d_ρ

1≦

d<sub>ρ

2</sub>≦

. . . ≦

d<sub>ρ

K</sub>, where ρ

₁=arg min_j d_j and ρ

_z=arg min<sub>j≠

{ρ

k}k=1z−

1</sub>(d_j) for 2≦

z≦

K

such that j represents an attribute out of a total number of K attributes.

19. The computing system claim 15, wherein the operations further comprise:

sending a distance value d_j to a user for attribute j, and receiving from the user a request for an increase in monetary retribution in exchange for selling aggregate data associated with attribute j to a customer.

20. The computing system of claim 15, wherein the operations further comprise:

re-computing a probability density function for attribute j using only data from those users that have indicated a willingness to share their attribute j data, and sharing the re-computed probability density function with a customer.