Selective privacy guarantees

• US 7,818,335 B2
• Filed: 12/22/2005
• Issued: 10/19/2010
• Est. Priority Date: 12/22/2005
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: McSherry, Frank D., Dwork, Cynthia
• Primary Examiner(s): Lu; Kuen S
• Application Number:
  US11/316,791
• Publication Number:
  US 20070147606A1
• Time in Patent Office: 1,762 Days
• Field of Search: 707/104.1, 707/101, 707/1, 707/769, 707/722
• US Class Current: 707/769
• CPC Class Codes: G06F 21/6254 by anonymising data, e.g. decorrelating personal data from the owner's identification

Abstract

Systems and methods are provided for selectively determining privacy guarantees. For example, a first class of data may be guaranteed a first level of privacy, while other data classes are only guaranteed some lesser level of privacy. An amount of privacy is guaranteed by adding noise values to database query outputs. Noise distributions can be tailored to be appropriate for the particular data in a given database by calculating a “diameter” of the data. When the distribution is based on the diameter of a first class of data, and the diameter measurement does not account for additional data in the database, the result is that query outputs leak information about the additional data.

Claims

1. A method for selectively determining privacy guarantees, comprising:

specifying at least one first class of data in a database, said database comprising data corresponding to said first class of data, and said database further comprising additional data;

calculating a first diameter for said first class of data;

calculating a first noise distribution at least in part using said first diameter,

wherein a first privacy parameter is at least in part used when calculating said first noise distribution;

performing a query over said first class of data and said additional data;

adding a noise value selected from said first noise distribution to an output of said query;

specifying at least one second class of data in the database;

calculating a second diameter for said second class of data; and

calculating a second noise distribution at least in part using said second diameter and a second privacy parameter.

2. The method of claim 1, wherein said first class of data is associated with a first class of people, and wherein said additional data is associated with a second class of people.

3. The method of claim 2, wherein said first class of people are people with a first risk of engaging in criminal behavior, and wherein said second class of people are people with a second risk of engaging in criminal behavior.

4. The method of claim 3, wherein said second risk is higher than said first risk.

5. The method of claim 3, wherein said criminal behavior comprises terrorism.

6. The method of claim 3, wherein said criminal behavior comprises trafficking of illegal drugs.

7. A method for selectively determining privacy guarantees, comprising:

specifying at least one first class of privacy principals, said first class of privacy principals being associated with a first class of data in a database;

specifying at least one second class of privacy principals, said second class of privacy principals being associated with said first class of data in a database, and said second class of privacy principals being further associated with a second class of data in a database;

calculating a diameter of said first class of data;

calculating a noise distribution at least in part using said diameter,

wherein a first privacy parameter is at least in part used when calculating said noise distribution;

adding a noise value selected from said noise distribution to a query output,

wherein a query associated with said query output is performed at least in part over said first class of privacy principals and at least in part over said second class of privacy principals;

calculating a second diameter for said second class of data; and

calculating a second noise distribution at least in part using said second diameter and a second privacy parameter.

8. The method of claim 7, wherein said at least one first class of privacy principals and said at least one second class of privacy principals comprise human beings.

9. The method of claim 8, wherein said first class of data in a database comprises personal data that does not substantially correlate with criminal behavior, and wherein said second class of data in a database comprises personal data that substantially correlates with criminal behavior.

10. The method of claim 9, wherein said criminal behavior comprises terrorism.

11. The method of claim 9, wherein said criminal behavior comprises trafficking of illegal drugs.

12. The method of claim 9, wherein said criminal behavior comprises violent crime.

13. The method of claim 9, wherein said criminal behavior comprises white collar crime.

14. The method of claim 8, wherein said first class of data in a database comprises personal data that does not substantially correlate with an infectious disease, and wherein said second class of data in a database comprises personal data that substantially correlates with an infectious disease.

15. A system for selectively guaranteeing privacy of data associated with privacy principals, comprising:

a database server;

a database comprising data associated with a plurality of privacy principals;

an interface for selecting a first class of data associated with said privacy principals,

wherein said interface allows selecting of a second class of data associated with said privacy principals, and for associating a first privacy parameter with said first class of data and a second privacy parameter with said second class of data;

a mechanism for calculating a diameter of said first class of data;

a mechanism for calculating a noise distribution at least in part using said diameter,

wherein a first privacy parameter is at least in part used when calculating said noise distribution;

a mechanism for selecting a noise value from said distribution and adding said noise value to a query output,

wherein a query associated with said query output is performed at least in part over said privacy principals;

a mechanism for calculating a second diameter for said second class of data; and

a mechanism for calculating a second noise distribution at least in part using said second diameter and said second privacy parameter.

16. The system of claim 15, wherein said interface allows for associating a first privacy parameter with said first class of data.

17. The system of claim 15, wherein said data associated with a plurality of privacy principals comprises personal data associated with a plurality of human beings.