Data diameter privacy policies

• US 20070124268A1
• Filed: 11/30/2005
• Published: 05/31/2007
• Est. Priority Date: 11/30/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,769,707 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 21/6227 where protection concerns the structure of data, e.g. records, types, queries
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes
• CPC Class Codes: G06Q 30/02 Marketing; Price estimation or determination; Fundraising
• CPC Class Codes: G06Q 50/26 Government or public services business processes related to the transportation industry G06Q50/40
• CPC Class Codes: G16H 70/00 ICT specially adapted for the handling or processing of medical references

Abstract

Privacy of data can be preserved while utility of the output is maximized by selecting from an appropriately calculated distribution of noise values to add to an output. A distribution that includes a high likelihood of large noise values may lead to less useful output data. Conversely, a distribution that includes very low likelihood of large noise values may lead to less privacy. A distribution should be calculated to provide an appropriate level of output utility and privacy based on the query that is performed and the desired privacy level.

Claims

1. A method for preserving privacy of data used in calculating an output, said method comprising:

performing a query over data, thereby obtaining an output;

calculating a noise distribution at least in part using a diameter of said query;

selecting a noise value from the noise distribution;

combining said noise value with the output.

2. The method of claim 1, wherein said data is in a database.

3. The method of claim 2, wherein said data in a database is associated with at least one privacy principal.

4. The method of claim 1, wherein said calculating a noise distribution further comprises at least in part using a privacy parameter, wherein said privacy parameter corresponds to an amount of privacy that is ensured.

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

6. The method of claim 1, wherein said noise distribution is a normal distribution.

7. The method of claim 1, wherein said noise distribution is a hybrid normal and exponential distribution, such that a normal distribution defines a portion of the distribution comprising the most probable noise values, and an exponential distribution defines a portion of the distribution comprising the least probable noise values.

8. The method of claim 1, wherein the data comprises medical information.

9. The method of claim 1, wherein the data comprises information submitted to a government agency.

10. The method of claim 1, wherein the data comprises information about company resources.

11. A system for generating a noisy output, wherein said system preserves privacy of data used in calculating said noisy output, said system comprising:

a database configured to store data associated with a plurality of privacy principals and configured to run queries on said data to obtain an output; and

a noise generation mechanism that at least in part utilizes a diameter of a query to produce a noise distribution, wherein a noise value is selected from said noise distribution and combined with the output.

12. The system of claim 11, further comprising query analysis mechanism for determining an appropriate diameter of a query.

13. The system of claim 12, wherein said query analysis mechanism is configured to recognize a query and retrieve an appropriate predetermined diameter.

14. The system of claim 11, wherein said noise generation mechanism is configured to modify said noise distribution using a privacy parameter, wherein said privacy parameter corresponds to an amount of privacy that is ensured.

15. The system of claim 11, wherein said noise distribution is an exponential distribution.

16. The system of claim 11, wherein said noise distribution is a normal distribution.

17. The system of claim 11, wherein said noise distribution is a hybrid normal and exponential distribution, such that a normal distribution defines a portion of the distribution comprising the most probable noise values, and an exponential distribution defines a portion of the distribution comprising the least probable noise values.

18. The system of claim 11, wherein the data comprises medical information.

19. The system of claim 11, wherein the data comprises information submitted to a government agency.

20. A method for determining an amount of privacy guaranteed to privacy principals supplying data, wherein said data is used in calculating a noisy output, said method comprising:

calculating a privacy parameter at least in part using a query diameter and a distribution of noise values.