Exponential noise distribution to optimize database privacy and output utility

• US 7,562,071 B2
• Filed: 12/02/2005
• Issued: 07/14/2009
• Est. Priority Date: 12/02/2005
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: McSherry, Frank D., Dwork, Cynthia
• Primary Examiner(s): MIZRAHI, DIANE D
• Application Number:
  US11/292,884
• Publication Number:
  US 20070130147A1
• Time in Patent Office: 1,320 Days
• Field of Search: 707 1- 10, 707100-1041, 707200-205
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2458 Special types of queries, e.g. statistical queries, fuzzy queries or distributed queries
• 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: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation

Abstract

An amount of noise to add to a query output may be selected to preserve privacy of inputs while maximizing utility of the released output. Noise values can be distributed according to a substantially symmetric exponential density function (“exponential distribution”). That is, the most likely noise value can be zero, and noise values of increasing absolute value can decrease in probability according to the exponential function.

Claims

1. A method for producing a noisy output that reduces predictability of data inputs while increasing accuracy of said noisy output, the method comprising:

formulating a query against data associated with a plurality of privacy principals and stored in a database;

evaluating the query to determine a query diameter measurement;

performing the query on one or more data inputs;

calculating by a computer processor an output of the query;

calculating by a computer processor a substantially exponential distribution of noise values as a function of the query diameter measurement and a privacy parameter, the substantially exponential distribution being calculated according to a Laplacian distribution;

combining by a computer processor said output with a noise value selected from the calculated substantially exponential distribution of noise values to produce the noisy output; and

disclosing the noisy output.

2. The method of claim 1, wherein evaluating the query to determine the query diameter measurement comprises determining a maximum difference in the output from varying data associated with a first privacy principal while holding constant data associated with at least one second privacy principal.

3. The method of claim 1, further comprising revealing said substantially exponential distribution, and revealing said privacy parameter.

4. The method of claim 1, wherein said substantially exponential distribution comprises an exponential distribution.

5. The method of claim 1, wherein said substantially exponential distribution comprises a center portion defined by a normal distribution.

6. A computer storage medium having stored thereon computer executable instructions executed by a computer processor for producing a noisy output that reduces predictability of data inputs while increasing accuracy of said noisy output comprising:

formulating a query against data associated with a plurality of privacy principals and stored in a database;

evaluating the query to determine a query diameter measurement;

performing the query on one or more data inputs;

calculating an output of the query;

calculating a substantially exponential distribution of noise values as a function of the query diameter measurement and a privacy parameter, the substantially exponential distribution being calculated according to a Laplacian distribution;

combining said output with a noise value selected from the calculated substantially exponential distribution of noise values to produce the noisy output; and

disclosing the noisy output.

7. The computer storage medium of claim 6, wherein evaluating the query to determine the query diameter measurement comprises determining a maximum difference in the output from varying data associated with a first privacy principal while holding constant data associated with at least one second privacy principal.

8. The computer storage medium of claim 6, wherein the instructions further comprise revealing said substantially exponential distribution, and revealing said privacy parameter.

9. The computer storage medium of claim 6, wherein said substantially exponential distribution comprises an exponential distribution.

10. The computer storage medium of claim 6, wherein said substantially exponential distribution comprises a center portion defined by a normal distribution.

11. A system for producing a noisy output that reduces predictability of data inputs while increasing accuracy of said noisy output, the system comprising:

a computer processor; and

a memory having stored therein instructions comprising;

formulating a query against data associated with a plurality of privacy principals and stored in a database;

evaluating the query to determine a query diameter measurement;

performing the query on one or more data inputs;

calculating an output of the query;

calculating a substantially exponential distribution of noise values as a function of the query diameter measurement and a privacy parameter, the substantially exponential distribution being calculated according to a Laplacian distribution;

combining said output with a noise value selected from the calculated substantially exponential distribution of noise values to produce the noisy output; and

disclosing the noisy output.

12. The system of claim 11, wherein evaluating the query to determine the query diameter measurement comprises determining a maximum difference in the output from varying data associated with a first privacy principal while holding constant data associated with at least one second privacy principal.

13. The system of claim 11, wherein the instructions further comprise revealing said substantially exponential distribution, and revealing said privacy parameter.

14. The system of claim 11, wherein said substantially exponential distribution comprises an exponential distribution.

15. The system of claim 11, wherein said substantially exponential distribution comprises a center portion defined by a normal distribution.