Answering n{2+o(1)} counting queries with differential privacy is hard

By Jonathan Ullman. 2012

101 citations recorded by the source corpus.

A central problem in differentially private data analysis is how to design efficient algorithms capable of answering large numbers of counting queries on a sensitive database. Counting queries are of the form "What fraction of individual records in the database satisfy the property q?" We prove that if one-way functions exist, then there is no algorithm that takes as input a database db ∈ dbset, and k = ~Θ(n2) arbitrary efficiently computable counting queries, runs in time poly(d, n), and returns an approximate answer to each query, while satisfying differential privacy. We also consider the complexity of answering "simple" counting queries, and make some progress in this direction by showing that the above result holds even when we require that the queries are computable by constant-depth (AC0) circuits. Our result is almost tight because it is known that ~Ω(n2) counting queries can be answered efficiently while satisfying differential privacy. Moreover, many more than n2 queries (even exponential in n) can be answered in exponential time. We prove our results by extending the connection between differentially private query release and cryptographic traitor-tracing schemes to the setting where the queries are given to the sanitizer as input, and by constructing a traitor-tracing scheme that is secure in this setting.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Differentially Private Password Frequency Lists (2016, background): “The key algorithmic challenge is developing an efficient algorithm to sample from the exponential mechanism for integer partitions — a straightforward implementation would require exponential time and space and there is strong evidence that sampling from the exponential mechanism is computationally ”
Fingerprinting codes and the price of approximate differential privacy (2013, background): “These works show that these families can have sample complexity lower than ˜ O ( √ d log |Q| /α 2 ).”
Between Pure and Approximate Differential Privacy (2015, background): “A formal privacy guarantee is given by (ε,δ)-differential privacy [DMNS06, DKM+06], which ensures that no individual’s data has a significant influence on the information released about the database.”
Private Learning and Sanitization: Pure vs. Approximate Differential Privacy (2013, background): “Work done in part while the third author was visiting Harvard University supported by NSF grant CNS-1237235 and a gift from Google, Inc. Contents”
Private Multiplicative Weights Beyond Linear Queries (2014, methodology): “We would like to thank Adam Smith and Salil Vadhan for helpful discussions.”
How to Use Heuristics for Differential Privacy (2018, background): “These hardness results extend even to providing numeric answers to more than quadratically many statistical queries [Ull16].”
Sample Complexity Bounds on Differentially Private Learning via Communication Complexity (2014, background): “Aside from sample complexity this problem is also computationally intractable for many interesting classesC (see [Ullman, 2013] and references therein for recent progress).”
FINGERPRINTING CODES AND THE PRICE OF APPROXIMATE DIFFERENTIAL PRIVACY∗ (2018, methodology): “1 is by replacing the one-way functions in [51] with a random oracle, and thereby obtain an information-theoretically secure traitor-tracing scheme.”
Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation (2014, background): “Ullman [70] shows that, assuming one-way functions exist, there is no algorithm that takes a database of N records of size λ and an arbitrary set of approximately O(N 2) queries, and approximately answers each query in time poly(N , λ) while preserving differential privacy.”
Differentially Private Data Publishing and Analysis: A Survey (2017, unknown): “[49] showed that among all computationally efficient algorithms, the Laplace mechanism is almost optimal.”