Fingerprinting codes and the price of approximate differential privacy

By Mark Bun, Jonathan Ullman, Salil P. Vadhan. 2013

237 citations recorded by the source corpus.

We show new lower bounds on the sample complexity of (ε, δ)-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database D ∈ ({0, 1}d)n has the form "What fraction of the individual records in the database satisfy the property q?" We show that in order to answer an arbitrary set Q of » nd counting queries on D to within error ±α it is necessary that [EQUATION] This bound is optimal up to poly-logarithmic factors, as demonstrated by the Private Multiplicative Weights algorithm (Hardt and Rothblum, FOCS'10). It is also the first to show that the sample complexity required for (ε, δ)-differential privacy is asymptotically larger than what is required merely for accuracy, which is O(log |Q|/α2). In addition, we show that our lower bound holds for the specific case of k-way marginal queries (where |Q| = 2k(d/k)) when α is a constant. Our results rely on the existence of short fingerprinting codes (Boneh and Shaw, CRYPTO'95; Tardos, STOC'03), which we show are closely connected to the sample complexity of differentially private data release. We also give a new method for combining certain types of sample complexity lower bounds into stronger lower bounds.

Subfields: Artificial Intelligence, Privacy & Security

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

In Privacy & Security

Citations in the corpus

The structure of optimal private tests for simple hypotheses (2018, background): “[15, 35]), and we remain far from a general characterization of the statistical cost of privacy.”
Tight Lower Bounds for Differentially Private Selection (2017, methodology): “To illustrate the versatility of Theorem 3, we show how it implies known lower bounds for releasing the mean of the dataset [16], [17], [18].”
Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, background): “This lemma is based on the results of [25] and [8], however, for the sake of completeness, we give a detailed proof of this lemma in Appendix C.”
Robust Traceability from Trace Amounts (2015, background): “• Work on fingerprinting attacks [14], [18] corresponds to our setting of a constant α, but assumes that p is drawn from a specific distribution D, and the attacker A knows p exactly (essentially, an infinite reference pool).”
The Price of Selection in Differential Privacy (2017, methodology): “The seminal work of Dinur and Nissim (2003) established a “price of privacy”: If we want to release the answer to & n statistics on a dataset of n individuals, then we must add noise whose magnitude is at least the same order as the sampling error of ≈ 1/ √ n, or else an attacker can reconstruct nea”
Between Pure and Approximate Differential Privacy (2015, methodology): “(Bun et al., 2014) showed that fingerprinting codes can be used to construct an attack demonstrating that any mechanism that accurately answers one-way marginals is not differentially private.”
Make Up Your Mind: The Price of Online Queries in Differential Privacy (2016, methodology): “Our algorithm and its analysis follow the reduction of Bun et al. [2015] for reducing the (offline) query release problem for thresholds to the offline interior point problem.”
Private Multiplicative Weights Beyond Linear Queries (2014, methodology): “We do so via an extension of the simple and elegant private multiplicativeweights framework of Hardt and Rothblum [19], which is known to achieve asymptotically optimal worst-case accuracy [6] and worst-case running time [29] for answering large families of linear queries.”
Interactive fingerprinting codes and the hardness of preventing false discovery (2014, methodology): “Another twist on fingerprinting codes is robustness Bun et al. (2014). Suppose that the consistency constraint only holds for (1 − β)` choices of j ∈ [`]. That is to say, the colluding users can somehow remove a β fraction of the watermarks. Bun et al. (2014) showed how to modify the Tardos fingerpr”
Simultaneous Private Learning of Multiple Concepts (2015, methodology): “†Supported by NSF grant CNS-1237235, a gift from Google, Inc. to Salil Vadhan, a Simons Investigator grant, and ISF grant 276/12.”
Generalized Gaussian Mechanism for Differential Privacy (2016, background): “The setting for the examination on the tail probability and dispersion in Section 3 is different from, though related to, the work on upper and lower bounds on sample complexity – the required sample size n to reach a certain level of accuracy α and privacy guarantee ( , δ) for count queries [18, 23”
The Large Margin Mechanism for Differentially Private Maximization (2014, unknown): “Lower bounds for approximate differential privacy have been shown by [7, 16, 11, 9], and the proof of our Theorem 1 borrows some techniques from [11].”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, background): “, [8, 25]), including a number of striking separations from nonprivate algorithms [11, 5, 2].”
The power of factorization mechanisms in local and central differential privacy (2019, background): “The power of diﬀerentially private algorithms for answering a worst-case workload of linear queries is well understood [BUV14], and known bounds are essentially tight as a function of the dataset size, the data domain, and the size of the workload.”
Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (2019, background): “Upper and lower bounds for learning the mean of a product distribution over the hypercube in `∞-distance include [12, 14, 32, 61].”