# US 10,121,024 B2 · Differentially private linear queries on histograms > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,121,024 B2 - Document ID: US10121024B2 - Status: Granted - Kind: B2 - Application number: 15/587,164 - Filed: 2017-05-04 - Published: 2017-08-17 - Granted: 2018-11-06 - Earliest claimed: 2013-03-15 - Assignees: Microsoft Technology Licensing, LLC - Applicants: Microsoft Technology Licensing, LLC - Inventors: Li Zhang; Kunal Talwar; Aleksandar Nikolov - Web page: https://patentgrep.com/patent/US10121024B2 ## CPC - G06F 21/6245: {Protecting personal data, e.g. for financial or medical purposes} - G06F 16/2455: Query execution - G06F 16/248: Presentation of query results - 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)} - G06F 21/60: Protecting data - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## 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 ### Claim 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. ### Claim 2 (depends on 1) The computer system of claim 1, wherein the access request is a counting query. ### Claim 3 (depends on 1) 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. ### Claim 4 (depends on 1) The computer system of claim 1, wherein applying the privacy protections is based on a size of the dataset. ### Claim 5 (depends on 1) 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. ### Claim 6 (depends on 1) 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. ### Claim 7 (depends on 1) 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. ### Claim 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. ### Claim 9 (depends on 8) The method of claim 8, wherein the access request is a counting query. ### Claim 10 (depends on 8) 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. ### Claim 11 (depends on 8) The method of claim 8, wherein applying the privacy protections is based on a size of the dataset. ### Claim 12 (depends on 8) 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. ### Claim 13 (depends on 8) 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. ### Claim 14 (depends on 8) 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. ### Claim 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. ### Claim 16 (depends on 15) The one or more hardware storage devices of claim 15, wherein the access request is a counting query. ### Claim 17 (depends on 15) 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. ### Claim 18 (depends on 15) The one or more hardware storage devices of claim 15, wherein applying the privacy protections is based on a size of the dataset. ### Claim 19 (depends on 15) 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. ### Claim 20 (depends on 15) 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. ### Claim 21 (depends on 1) 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.