Differentially private linear queries on histograms
First Claim
1. A method comprising:
- receiving a dataset from a memory of a computing device;
receiving a query by the computing device through a network;
performing base decomposition using the dataset and the query to generate an orthonormal basis, by the computing device;
generating an answer to the query by the computing device;
adding noise to the answer, by the computing device, using the orthonormal basis, to protect differential privacy of the dataset stored in the memory of the computing device by preventing the determination of the presence or absence of a value from the dataset based on the answer with the added noise; and
providing the answer with the added noise by the computing device through the network.
2 Assignments
0 Petitions
Accused Products
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.
21 Citations
29 Claims
-
1. A method comprising:
-
receiving a dataset from a memory of a computing device; receiving a query by the computing device through a network; performing base decomposition using the dataset and the query to generate an orthonormal basis, by the computing device; generating an answer to the query by the computing device; adding noise to the answer, by the computing device, using the orthonormal basis, to protect differential privacy of the dataset stored in the memory of the computing device by preventing the determination of the presence or absence of a value from the dataset based on the answer with the added noise; and providing the answer with the added noise by the computing device through the network. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11)
-
-
12. A method comprising:
-
receiving a query at a computing device through a network; determining an answer to the query, by the computing device, using a database stored in a memory of the computing device; performing base decomposition using the database and the query, by the computing device, to generate an orthonormal basis; adding noise to the answer, by the computing device, using the orthonormal basis, to protect differential privacy of the database stored in the memory of the computing device by preventing the determination of the presence or absence of a value from the database based on the answer with the added noise; and providing the answer with the added noise by the computing device through the network. - View Dependent Claims (13, 14, 18)
-
-
15. An apparatus comprising:
-
a processor; a memory; a privacy protector that; receives a dataset from the memory; receives a query through a network; performs base decomposition using the dataset and the query to generate an orthonormal basis; generates an answer to the query; adds noise to the answer using the orthonormal basis to protect the differential privacy of the dataset stored in the memory by preventing the determination of the presence or absence of a value from the dataset based on the answer with the added noise; and provides the answer with the added noise through the network. - View Dependent Claims (16, 17, 19, 20, 21, 22, 23, 24, 25)
-
-
26. An apparatus comprising:
-
a processor; a memory; and a privacy protector that; receives a query through a network; determines an answer to the query using a database, wherein the database is stored in the memory; performs base decomposition using the database and the query to generate an orthonormal basis; adds noise to the answer using the orthonormal basis, to protect differential privacy of the database stored in the memory by preventing the determination of the presence or absence of a value from the database based on the answer with the added noise; and provides the answer with the added noise through the network. - View Dependent Claims (27, 28, 29)
-
Specification