Differentially private linear queries on histograms

• US 10,121,024 B2
• Filed: 05/04/2017
• Issued: 11/06/2018
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Inventors: Zhang, Li, Talwar, Kunal, Nikolov, Aleksandar
• Primary Examiner(s): Jeudy, Josnel
• Application Number:
  US15/587,164
• Publication Number:
  US 20170235974A1
• Time in Patent Office: 551 Days
• 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 computer system comprising:

one or more processors; and

one or more computer-readable hardware storage media having stored thereon computer-executable instructions that are executable by the one or more processors to cause the computer system to operate with a computing environment that improves how data is prepared for examination by selectively imposing differential privacy constraints on the data by causing the computer system to;

receive a request to access information included in a dataset that includes confidential information, wherein the dataset has associated therewith a corresponding histogram such that the access request is directed to the dataset'"'"'s histogram, and wherein the access request is received from a source that is not authorized to view an originating identity of the confidential information;

query the dataset to obtain a response to the access request, wherein the response includes a set of collected information, the set of collected information including at least some of the confidential information;

after determining that the response includes the at least some of the confidential information, apply privacy protections to the set of collected information included in the response, wherein applying the privacy protections to the set of collected information alters the set of collected information and causes the originating identity of the confidential information to be hidden; and

after applying the privacy protections to the set of collected information included in the response, return the response to the source of the access request, and in such a manner that the response is viewable without causing the at least some of the confidential information to be discernable.

2. The computer system of claim 1, wherein the access request is a counting query.

3. The computer system of claim 1, wherein determining how much privacy protections to apply to the set of collected information is based on a size of the dataset, whereby datasets that have relatively less data receive less privacy protections than datasets that have relatively more data.

4. The computer system of claim 1, wherein applying the privacy protections is based on a size of the dataset.

5. The computer system of claim 1, wherein returning the response to the source of the access request comprises publishing the response and causing the response to be downloadable.

6. The computer system of claim 1, wherein altering the set of collected information comprises introducing a determined amount of gaussian noise into the set of collected information.

7. The computer system of claim 1, wherein the privacy protections are based on one or more predetermined privacy guarantees, the one or more predetermined privacy guarantees being configured by an administrator of the dataset.

21. The computer system of claim 1, wherein applying the privacy protections to the set of collected information is based on an amount of sparseness of the histogram.

8. A method for operating a computing environment that improves how data is prepared for examination by selectively imposing differential privacy constraints on the data, the method being implemented by one or more processors of a computer system that operates with the computing environment, the method comprising:

receiving a request to access information included in a dataset that includes confidential information, wherein the dataset has associated therewith a corresponding histogram such that the access request is directed to the dataset'"'"'s histogram, and wherein the access request is received from a source that is not authorized to view an originating identity of the confidential information;

querying the dataset to obtain a response to the access request, wherein the response includes a set of collected information, the set of collected information including at least some of the confidential information;

after determining that the response includes the at least some of the confidential information, applying privacy protections to the set of collected information included in the response, wherein applying the privacy protections to the set of collected information alters the set of collected information and causes the originating identity of the confidential information to be hidden; and

after applying the privacy protections to the set of collected information included in the response, returning the response to the source of the access request, and in such a manner that the response is viewable without causing the at least some of the confidential information to be discernable.

9. The method of claim 8, wherein the access request is a counting query.

10. The method of claim 8, wherein determining how much privacy protections to apply to the set of collected information is based on a size of the dataset, whereby datasets that have relatively less data receive less privacy protections than datasets that have relatively more data.

11. The method of claim 8, wherein applying the privacy protections is based on a size of the dataset.

12. The method of claim 8, wherein returning the response to the source of the access request comprises publishing the response and causing the response to be downloadable.

13. The method of claim 8, wherein altering the set of collected information comprises introducing a determined amount of gaussian noise into the set of collected information.

14. The method of claim 8, wherein the privacy protections are based on one or more predetermined privacy guarantees, the one or more predetermined privacy guarantees being configured by an administrator of the dataset.

15. One or more hardware storage devices having stored thereon computer-executable instructions that are executable by one or more processors of a computer system to cause the computer system to operate with a computing environment that improves how data is prepared for examination by selectively imposing differential privacy constraints on the data by causing the computer system to:

receive a request to access information included in a dataset that includes confidential information, wherein the dataset has associated therewith a corresponding histogram such that the access request is directed to the dataset'"'"'s histogram, and wherein the access request is received from a source that is not authorized to view an originating identity of the confidential information;

query the dataset to obtain a response to the access request, wherein the response includes a set of collected information, the set of collected information including at least some of the confidential information;

after determining that the response includes the at least some of the confidential information, apply privacy protections to the set of collected information included in the response, wherein applying the privacy protections to the set of collected information alters the set of collected information and causes the originating identity of the confidential information to be hidden; and

after applying the privacy protections to the set of collected information included in the response, return the response to the source of the access request, and in such a manner that the response is viewable without causing the at least some of the confidential information to be discernable.

16. The one or more hardware storage devices of claim 15, wherein the access request is a counting query.

17. The one or more hardware storage devices of claim 15, wherein determining how much privacy protections to apply to the set of collected information is based on a size of the dataset, whereby datasets that have relatively less data receive less privacy protections than datasets that have relatively more data.

18. The one or more hardware storage devices of claim 15, wherein applying the privacy protections is based on a size of the dataset.

19. The one or more hardware storage devices of claim 15, wherein returning the response to the source of the access request comprises publishing the response and causing the response to be downloadable, and wherein altering the set of collected information comprises introducing a determined amount of gaussian noise into the set of collected information.

20. The one or more hardware storage devices of claim 15, wherein the privacy protections are based on one or more predetermined privacy guarantees, the one or more predetermined privacy guarantees being configured by an administrator of the dataset.