Differential data privacy

• US 20070143289A1
• Filed: 12/16/2005
• Published: 06/21/2007
• Est. Priority Date: 12/16/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Dwork, Cynthia, McSherry, Frank
• Granted Patent: US 7,698,250 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes

Abstract

Systems and methods are provided for controlling privacy loss associated with database participation. In general, privacy loss can be evaluated based on information available to a hypothetical adversary with access to a database under two scenarios: a first scenario in which the database does not contain data about a particular privacy principal, and a second scenario in which the database does contain data about the privacy principal. Such evaluation can be made for example by a mechanism for determining sensitivity of at least one database query output to addition to the database of data associated with a privacy principal. An appropriate noise distribution can be calculated based on the sensitivity measurement and optionally a privacy parameter. A noise value is selected from the distribution and added to query outputs.

Claims

1. A method for controlling privacy loss of a privacy principal, comprising:

determining first information that would be available to an adversary with access to a database query output, said database not containing data associated with the privacy principal;

determining second information that would be available to said adversary with access to a second database query output, said second database containing data associated with the privacy principal; and

determining a distribution of noise values to combine with a database query output such that said second information differs from said first information by an amount associated with a privacy parameter.

2. The method of claim 1, wherein the privacy parameter is chosen by the privacy principal.

3. The method of claim 1, further comprising adding a noise value from said distribution of noise values to said database query output.

4. The method of claim 1, further comprising advertising the privacy parameter and a corresponding amount of privacy loss.

5. The method of claim 1, wherein the distribution is an exponential distribution.

6. The method of claim 1, further comprising selecting a privacy parameter associated with a minimum amount of privacy loss from a plurality of privacy parameters provided by a plurality of privacy principals.

7. The method of claim 1, wherein the privacy principal is a person.

8. A system for interactively controlling privacy loss, comprising:

an interface for accepting at least one privacy parameter from at least one privacy principal, wherein the privacy parameter is associated with an amount of privacy loss that is acceptable to said privacy principal;

a database;

a mechanism for determining sensitivity of at least one database query output to addition to the database of data associated with said privacy principal; and

a mechanism for combining noise with database query outputs, wherein the noise is selected from a distribution that is calculated using said privacy parameter and said sensitivity of the database.

9. The system of claim 8, wherein said distribution is calculated using a most restrictive privacy parameter selected from a plurality of privacy parameters.

10. The system of claim 8, wherein said mechanism for determining sensitivity comprises:

computer readable instructions for determining first information that would be available to an adversary with access to a first database query output, said first database not containing data associated with the privacy principal; and

computer readable instructions for determining second information that would be available to said adversary with access to a second database query output, said second database containing data associated with the privacy principal.

11. The system of claim 8, further comprising a mechanism for releasing a noisy database query output produced by said mechanism for combining.

12. The system of claim 8, said interface further comprising a demonstration of how to choose a privacy parameter associated with an amount of privacy loss that is acceptable to said privacy principal.

13. The system of claim 8, said interface further comprising a demonstration of an amount of privacy loss associated with a restrictive privacy parameter and an amount of privacy loss associated with an unrestrictive privacy parameter.

14. The system of claim 8, wherein the distribution is an exponential distribution.

15. A computer readable medium bearing instructions for preserving privacy of a privacy principal that contributes data to a database, comprising:

instructions for combining noise with database query outputs, wherein the noise is selected from a noise distribution, wherein said noise distribution is calculated using an output sensitivity and a privacy parameter, said output sensitivity being a measure of change in a database query output due to addition to the database of data associated with said privacy principal, and said privacy parameter being associated with an amount of privacy loss.

16. The computer readable medium of claim 15, wherein the noise distribution is an exponential noise distribution.

17. The computer readable medium of claim 15, further comprising instructions for an interface for entry of the privacy parameter by the privacy principal.

18. The computer readable medium of claim 15, further comprising instructions for selecting a privacy parameter associated with a minimum amount of privacy loss from a plurality of privacy parameters provided by a plurality of privacy principals.

19. The computer readable medium of claim 15, further comprising instructions for calculating said noise distribution.

20. The computer readable medium of claim 15, wherein said data associated with said privacy principal comprises data submitted to a government agency.