The Small-Database Mechanism (SmallDB), lower bounds, differential privacy and game theory

Before ThisWhere Lecture 14 Left Off

Lecture 14 gave the budget its square root. Advanced composition (the theorem that tracks privacy loss across many mechanisms) bounds the cumulative loss of $k$ mechanisms by a term growing like $\sqrt{k}$, plus a second-order term, at the price of a slack $\delta'$. The proof runs through a reduction to binary(ish) mechanisms and a Hoeffding bound (a concentration inequality for sums of independent random variables). The exponential mechanism then generalized the output type. Any score function on candidate objects becomes a private sampler, with privacy set by the score sensitivity (how much one row can change the score) and accuracy logarithmic in the number of objects. The applications ended at batch query answering, where the Gaussian mechanism (which adds normally distributed noise) plus advanced composition answers $o(n^2)$ queries accurately and the error grows too large beyond that.

This LectureWhat It Adds

This lecture crosses the $n^2$ barrier and then proves barriers of its own. The Small-Database Mechanism (SmallDB) applies the exponential mechanism to synthetic datasets. It releases a small database of $m = O(\log|\mathcal{Q}|/\alpha^2)$ rows that approximates every query in a family, with error $O(\sqrt{\log|\mathcal{X}| \cdot \log|\mathcal{Q}|}/(\eps n))$, far beyond $n^2$ queries, at exponential running time in $d$. The lower bounds show the costs are inherent. The reconstruction theorem says answers to all $2^n$ subset queries with error $\alpha$ determine the dataset up to $4\alpha n$ row flips, so $\alpha \le 1/40$ is blatant non-privacy (a near-complete reconstruction of the dataset), and Dinur-Nissim make the attack efficient. The computational lower bound reduces traitor tracing (a scheme that identifies which keys built a pirate decoder) to private query answering. A polynomial-time $(1, 1/10n)$-Differentially Private (DP) mechanism for more than $O(n^2)$ queries would trace pirates, contradicting one-way functions (functions that are easy to compute but hard to invert). The lecture ends on incentives. Differential privacy makes truth-telling an approximately dominant strategy (a choice that is nearly best whatever the other players do), composition and collusion resistance (no group of players gains by deviating together) included. The verification problem is the case where no outcome is ever observed. The final slide restates the fundamental law: overly accurate estimates of too many statistics are blatantly non-private.

Study PlanWhat to Read, in Lecture Order

1. Chapter 5 §10: SmallDB. The theorem, the weight function as an exponential-mechanism score, the two halves of the accuracy proof, the exponential running time and private multiplicative weights (an iterative algorithm that reweights a candidate dataset after each query) as the efficient alternative.
2. §11: Reconstruction. Blatant non-privacy (a near-complete reconstruction of the dataset), the $4\alpha$ bound through $q_x$ and $q_{\bar{x}}$ (the answer vectors on the dataset and its complement), the $1/40$ corollary and the Dinur-Nissim efficient variant. Step through the stage, then run the reconstruction lab at $\alpha = 1/40$.
3. §12: Traitor tracing (a scheme that identifies which keys built a pirate decoder). The scheme, the pirate models, the four-step reduction to the computational lower bound, the simple construction with hybrid ciphertexts and the signature-based hardness of synthetic data.
4. §13: Game theory. Incentives, approximate truthfulness under composition and collusion (players coordinating their deviations), the bad news about arbitrary reports, correlated equilibria (outcomes where each player follows a shared recommendation) and the verification problem (where no outcome of the game is ever observed).

PracticeExercises for This Lecture

• The reconstruction bound, reproducing $d(x, x')/n \le 4\alpha$ (the fraction of rows on which the two datasets differ) and evaluating it at $\alpha = 1/40$.