Source-linked AI summary
Fingerprinting Codes and the Price of Approximate Differential Privacy
Mark Bun, Jonathan Ullman, Salil Vadhan
TL;DR
The paper studies whether approximate differential privacy adds sample complexity beyond statistical accuracy when answering large sets of counting queries. It uses fingerprinting codes and a composition theorem to prove lower bounds, including for k-way marginals. The resulting bounds are nearly optimal and establish a privacy price for high-dimensional data.
Problem
The paper asks whether approximate differential privacy requires asymptotically more samples than statistical accuracy alone for large counting-query families.
Method
The paper directly uses short fingerprinting codes to derive information-theoretic lower bounds and combines lower-bound techniques through a composition theorem.
Results
For arbitrary large query sets, the paper proves n ≥̃Ω(√d log |Q|/(α^2 ε)), a bound nearly matched by private multiplicative weights.
Takeaways & Limitations
The results establish a price of approximate differential privacy for high-dimensional datasets and extend nearly matching lower bounds to k-way marginal queries when α is not too small.
Abstract
from arXiv · showhide
We show new lower bounds on the sample complexity of $(\varepsilon, δ)$-differentially private algorithms that accurately answer large sets of counting queries. A counting query on a database $D \in (\{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 $\mathcal{Q}$ of $\gg nd$ counting queries on $D$ to within error $\pm α$ it is necessary that $$ n \geq \tildeΩ\Bigg(\frac{\sqrt{d} \log |\mathcal{Q}|}{α^2 \varepsilon} \Bigg). $$ This bound is optimal up to poly-logarithmic factors, as demonstrated by the Private Multiplicative Weights algorithm (Hardt and Rothblum, FOCS'10). In particular, our lower bound is the first to show that the sample complexity required for accuracy and $(\varepsilon, δ)$-differential privacy is asymptotically larger than what is required merely for accuracy, which is $O(\log |\mathcal{Q}| / α^2)$. In addition, we show that our lower bound holds for the specific case of $k$-way marginal queries (where $|\mathcal{Q}| = 2^k \binom{d}{k}$) when $α$ is not too small compared to $d$ (e.g. when $α$ is any fixed constant). Our results rely on the existence of short \emph{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.
1 Introduction
The paper asks whether approximate differential privacy imposes an additional sample-complexity cost beyond statistical accuracy, and answers yes for high-dimensional datasets and large counting-query families. It derives lower bounds using fingerprinting codes and extends them to k-way marginals under stated accuracy conditions.
- Motivation: The central question is whether achieving statistical accuracy and (ε, δ)-differential privacy requires more samples than statistical accuracy alone.For large query families, statistical accuracy alone needs Θ(log |Q|/α^2) samples.
- Contribution: The paper closes the gap by showing a price of approximate differential privacy for high-dimensional datasets.Earlier work had no lower bounds separating privacy from statistical-accuracy sample complexity.
- Counting queries: For arbitrary large query sets, the lower bound is n ≥̃Ω(√d log |Q|/(α^2 ε)), and it is nearly matched by private multiplicative weights.A composition theorem combines this result with existing lower bounds to obtain the stronger bound as a function of |Q|, d, and α.
- Scope conditions: The general query-set theorem requires sufficiently small α, d ≥ 6 log(1/α), and s ≥ d/α^2; these conditions are described as necessary or mild.The paper notes that noisy histograms and independent noise provide better bounds outside these parameter regimes.
- k-way marginals: The lower bound also applies to k-way marginal queries when α is not too small, including any fixed constant α.Theorem 1.3 covers α smaller than a universal constant and larger than an inverse polynomial in d.
- Techniques: Fingerprinting codes yield information-theoretic sample-complexity lower bounds for privately releasing answers to counting queries.For 1-way marginals, accurate answers can form a codeword satisfying the marking assumption, enabling tracing that conflicts with differential privacy.
2 Preliminaries
This section defines the privacy, accuracy, query, and sample-complexity framework, then describes re-identification as the route from accurate answers to privacy lower bounds.
- A database is an ordered n-row tuple from a data universe X, with adjacency defined by changing one row.
- (ε, δ)-differential privacy constrains randomized algorithms on adjacent databases.
- A counting query evaluates a predicate’s average over database rows, and (α, β)-accuracy permits error at most α for at least 1 − β of queries.
- Sample complexity is the least database size supporting both specified query accuracy and differential privacy.
- For constant ε and δ = o(1/n), lower bounds for constant accuracy can translate into bounds scaling as 1/α.
- Re-identification attacks distinguish a sanitizer’s output on D from its output after removing one row, contradicting differential privacy when a row can be identified.
3 Lower Bounds via Fingerprinting Codes
The paper uses fingerprinting codes to convert accurate query answers into re-identification attacks, yielding privacy sample-complexity lower bounds for marginals and general query families.
- 1-way marginals: The resulting 1-way-marginal lower bound is asymptotically larger than the nonprivate Θ(log d) statistical-accuracy requirement.
- Fingerprinting codes: Fingerprinting codes encode users as rows of a randomized binary codebook and trace collusion outputs to a contributing user.
- Fingerprinting codes: Robust fingerprinting codes tolerate errors in a constant fraction of codeword coordinates while retaining nearly optimal user capacity.
- 1-way marginals: For 1-way marginals, accurate answers enable re-identification through fingerprinting-code tracing, ruling out private accurate release below the code length.
- Product distributions: The same construction yields minimax lower bounds for privately inferring marginals of product distributions.
- General query families: Generalized fingerprinting codes for a query family Q imply sample-complexity lower bounds, while weak codes are essentially equivalent to such lower bounds.
- General query families: A weak fingerprinting code also yields privacy parameters transformed to (ε/2, δ/(2e^ε/2n)) for accurate release.
4 A Composition Theorem for Sample Complexity
The composition theorem combines a reconstruction attack with a re-identifiable distribution to amplify sample-complexity lower bounds. It constructs product databases and query families whose lower bound scales as the product of the component bounds.
- Composition theorem: The composition theorem combines lower-bound instances for (Q, X) and (Q′, X′) into a related instance with target lower bound n · n′.The product query family is Q ∧Q′ = {q ∧q′ : q ∈Q, q′ ∈Q′}.
- Product construction: The product database D∗ contains n subdatabases D′_1, . . . , D′_n, with rows indexed by pairs from the two component databases.The shared subdatabase structure allows a member identified within one subdatabase to be identified in D∗.
- Product construction: A query q ∧q′ computes a subset-sum of the vector of q′ answers across the subdatabases of a product database.This lets approximate answers to product queries constrain and reconstruct answers on subdatabases.
- Reconstruction step: A reconstruction attack converts sufficiently accurate answers to Q ∧Q′ into accurate answers to Q′ on most subdatabases.The formal lemma accounts for query-wise accuracy and uses Markov’s inequality to control the fraction of unsuccessful subdatabases and queries.
5 Applications of the Composition Theorem
The composition theorem is applied to combine new 1-way marginal lower bounds with existing lower bounds, obtaining results for k-way marginals and arbitrary counting queries. The k-way marginal result applies when accuracy is not too small relative to d.
- Applications: The applications combine the new 1-way marginal lower bounds with variants of known lower bounds from the literature.The section specifically targets k-way marginal queries and arbitrary counting queries.
5.1 Lower Bounds for k-Way Marginals
The section derives lower bounds for privately answering k-way marginal queries by combining VC-dimension and reconstruction-based arguments. It establishes separate linear dependence on k and inverse-quadratic dependence on α, then composes these ingredients into stronger results under explicit parameter conditions.
- The Ω(k) Lower Bound: Ω(k) samples are necessary for privately answering k-way marginals, via their VC-dimension being at least k.The VC-dimension argument uses a shattered set of k records and a reconstruction attack from accurate answers.
- The Ω(k) Lower Bound: A 4α-reconstruction attack exists for any query family whose VC-dimension is n, using (α, 0)-accurate answers.The attack reconstructs a fractional vector from query answers by selecting a vector satisfying the accuracy constraints.
- The Ω(1/α^2) Lower Bound: Ω(1/α^2) samples are necessary for k-way marginals when α is sufficiently small, α ≥ 1/d^(.499k), and k is constant.The construction uses an ℓ1-minimization reconstruction attack supported by Euclidean-section and singular-value properties of a suitable database-query matrix.
- The Ω(1/α^2) Lower Bound: The reconstruction guarantee returns t with ∥t − s∥_1 ≤ α′ · n from (α, β)-accurate k-way marginal answers.The proof chooses n = Ω(1/α^2) so the reconstruction error is at most α′, while maintaining the matrix-dimension condition.
- Putting Together the Lower Bound: The composition argument first obtains re-identifiability from k-way marginal answers and then applies the VC-dimension reconstruction attack.The order is necessary because the VC-dimension attack requires (α, 0)-accuracy, whereas the composition theorem requires positive error probability β.
- Putting Together the Lower Bound: For k-way marginals, the combined theorem applies when ℓ + 2 ≤ k ≤ d and α is sufficiently small but at least 1/d^(.499ℓ).Under these conditions, the construction yields a distribution that is (1/2, o(1/n))-re-identifiable from (α, 0)-accurate answers.
5.2 Lower Bounds for Arbitrary Queries
The section establishes an Ω(1/α^2) lower bound for arbitrary counting queries through reconstruction attacks, then combines it with other lower bounds to obtain a nearly optimal bound. The reconstruction argument extends from Boolean to fractional vectors and uses random subset-sum queries with concentration analysis.
- Putting Together the Lower Bound: A composition theorem combines the arbitrary-query, 1-way-marginal, VC-dimension, and accuracy lower bounds into a nearly optimal bound in |Q|, d, and α.The resulting composition establishes the theorem stated in the introduction.
- The Ω(1/α^2) Lower Bound for Arbitrary Queries: Ω(1/α^2) samples are necessary for worst-case query families, via a reconstruction attack related to Dinur and Nissim’s seminal attack.The section contrasts this bound with the earlier Boolean-vector formulation and extends the framework to fractional vectors.
- The Ω(1/α^2) Lower Bound for Arbitrary Queries: Accurate query answers are interpreted as approximate subset-sums of a fractional vector s ∈ [0, 1]^n that the attack seeks to reconstruct.The attack searches a discretization of the unit interval for a vector consistent with the approximate subset-sums.
- The Ω(1/α^2) Lower Bound for Arbitrary Queries: For α ≤ κ^2/240 and n = 1/(576κ^2α^2), random subset-sums separate vectors with sufficiently large ℓ1 distance with constant probability.Berry–Esseen analysis establishes the subset-sum anti-concentration, while Chernoff concentration transfers the property to a sufficiently large random query family.
- The Ω(1/α^2) Lower Bound for Arbitrary Queries: For α′ ∈ (0, 1], α ≤ (α′)^2/960, and n = 1/(144(α′)^2α^2), some O(n log(1/α))-sized query family enables an α′-reconstruction attack from (α, 1/3)-accurate answers.The construction first gives an arbitrary-family reconstruction algorithm and then shows that a random query family succeeds for every fractional vector with non-zero probability.
- Putting Together the Lower Bound: For sufficiently small α > 2^(-d/6) and h ≤ 2^(d/3), query families of size O(hd log(1/α)/α^2) support generalized fingerprinting codes and re-identifiable database distributions.The corresponding guarantees use security (1/2, o(1/n)) for (α, 0)-accuracy and re-identification from (α, 0)-accurate answers.
6 Constructing Error-Robust Fingerprinting Codes
This section constructs fingerprinting codes that tolerate errors in a constant fraction of coordinates, by first establishing weak robustness for Tardos’ code and then amplifying it.
- The construction starts from Tardos’ nearly optimal code, which is not robust to any constant fraction of errors.The new code retains a nearly optimal number of users, losing only a constant factor.
- A marked column contains the same bit for every user, and an adversary can exploit enough marked columns to replace the codeword with an untraceable all-zero or all-one word.Tolerating a β fraction of all-coordinate errors requires at least βd marked columns.
- The authors do not optimize the tolerated error fraction and leave robustness arbitrarily close to 1/2 as an open problem.
- Weak robustness requires correctness on only a β fraction of marked positions, rather than a β fraction of all positions.This weaker property remains meaningful even when marked positions are sparse.
- 6.1 From Weak Error Robustness to Strong Error Robustness: A reduction converts weak robustness, together with sufficiently many 0-marked and 1-marked columns, into robustness for an Ω(β) fraction of errors with code length O(d).The reduction appends marked columns and randomly permutes the augmented codebook.
- 6.2 Weak Robustness of Tardos’ Fingerprinting Code: Tardos’ code is shown to be weakly robust to a 1/25 fraction of errors, and the combined construction is robust to a 1/75 fraction.The analysis bounds the negative score contribution caused by errors.
A Lower Bounds on Fingerprinting Codes via Differential Privacy
This section uses differential privacy to derive lower bounds on fingerprinting-code length, with Gaussian noise providing the privacy-based contradiction.
- Differential-privacy upper bounds for answering 1-way marginals imply lower bounds on the length of fingerprinting codes.The argument proceeds by contraposition.
- The resulting bound rules out an (n,d)-fingerprinting code with security ξ < 1/(6en) for the stated parameter relationship.
- The proof constructs a Gaussian-noise adversary, rounds the noisy marginal vector to bits, and outputs the resulting pirated codeword.The Gaussian coordinates have variance σ^2 = 2d ln(1/δ)/n^2.
- The contradiction follows by showing that the adversary produces feasible codewords with constant probability but cannot be traced successfully.