DIFFERENTIALLY PRIVATE LINEAR QUERIES ON HISTOGRAMS

• US 20140283091A1
• Filed: 03/15/2013
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Zhang, Li, Talwar, Kunal, Nikolov, Aleksandar
• Granted Patent: US 9,672,364 B2
• Time in Patent Office: Days
• US Class Current: 726/26
• CPC Class Codes: G06F 16/2455 Query execution
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 17/18 for evaluating statistical data , e.g. average values, frequency distributions, probability functions, regression analysis forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6245 Protecting personal data, e.g. for financial or medical purposes

Abstract

The privacy of linear queries on histograms is protected. A database containing private data is queried. Base decomposition is performed to recursively compute an orthonormal basis for the database space. Using correlated (or Gaussian) noise and/or least squares estimation, an answer having differential privacy is generated and provided in response to the query. In some implementations, the differential privacy is ε-differential privacy (pure differential privacy) or is (ε,δ)-differential privacy (i.e., approximate differential privacy). In some implementations, the data in the database may be dense. Such implementations may use correlated noise without using least squares estimation. In other implementations, the data in the database may be sparse. Such implementations may use least squares estimation with or without using correlated noise.

Claims

1. A method comprising:

receiving a dataset by a computing device;

receiving a query by the computing device;

performing base decomposition using the dataset and the query to generate an orthonormal basis, by the computing device;

generating an answer to the query;

adding noise to the answer, by the computing device, using at least one of correlated noise and least squares estimation; and

providing the answer with noise by the computing device.

2. The method of claim 1, wherein the dataset comprises a database.

3. The method of claim 1, wherein the query is a histogram.

4. The method of claim 1, wherein the query is a query matrix.

5. The method of claim 4, wherein performing the base decomposition comprises determining a set of orthonormal matrices and recursively computing an orthonormal basis for the dataset, based on a minimum volume enclosing ellipsoid of columns of the query matrix.

6. The method of claim 1, wherein adding noise to the answer using at least one of correlated noise and least squares estimation, comprises using the correlated noise to add noise to the answer, wherein using the correlated noise comprises:

computing a sequence of John ellipsoids and projections based on the query;

determining a correct answer for each of the projections;

adding Gaussian noise to each correct answer according to the corresponding John ellipsoid; and

combining the answers from at least two of the projections.

7. The method of claim 1, wherein adding noise to the answer using at least one of correlated noise and least squares estimation, comprises using the least squares estimation to add noise to the answer, wherein using the least squares estimation comprises:

receiving a noisy answer; and

performing the least squares estimation on the noisy answer to generate the answer with noise.

8. The method of claim 7, wherein the noisy answer is generated using correlated noise.

9. The method of claim 1, further comprising determining whether the dataset is dense or sparse, and adding noise to the answer using correlated noise if the dataset is dense, and adding noise to the answer using least squares estimation if the dataset is sparse.

10. The method of claim 1, further comprising generating the noise based on a privacy guarantee.

11. The method of claim 10, wherein the privacy guarantee comprises ε

-differential privacy or (ε

,δ

)-differential privacy.

12. A method comprising:

receiving a linear query at a computing device;

determining an answer to the linear query, by the computing device;

adding privacy to the answer, by the computing device, using at least one of correlated noise and least squares estimation; and

providing the answer with privacy by the computing device.

13. The method of claim 12, wherein the privacy comprises ε

-differential privacy or (ε

,δ

)-differential privacy.

14. The method of claim 12, wherein determining the answer to the linear query uses a database, wherein the database is dense or sparse.

15. The method of claim 14, wherein adding privacy to the answer comprises using correlated noise if the database is dense, and using least squares estimation if the database is sparse.

16. The method of claim 14, further comprising, prior to adding privacy to the answer, performing base decomposition using the database and the linear query to generate an orthonormal basis, wherein the orthonormal basis is used by the correlated noise and least squares estimation.

17. A system comprising:

a dataset provider that provides a dataset; and

a privacy protector that;

receives the dataset from the dataset provider, and receives a query;

determines whether the dataset is dense or sparse;

generates an answer to the query using the dataset and whether the dataset is dense or sparse, wherein the answer has differential privacy; and

provides the answer with differential privacy to a client device.

18. The system of claim 17, wherein the privacy protector performs base decomposition using the dataset and the query to generate an orthonormal basis, and uses the orthonormal basis in determining the differential privacy.

19. The system of claim 17, wherein the privacy protector provides the differential privacy to the answer using at least one of correlated noise and least squares estimation.

20. The system of claim 17, wherein the privacy protector provides the differential privacy to the answer using correlated noise if the dataset is dense, and provides the differential privacy to the answer using least squares estimation if the dataset is sparse.