Differential Privacy — Mechanisms, Composition, and Lower Bounds
Stub. The formal definition of differential privacy as the response to reconstruction attacks; the standard mechanisms for achieving it (Laplace and Gaussian noise addition, the exponential mechanism) and how privacy loss composes across multiple queries; and information-theoretic lower bounds showing a minimum amount of noise (or error) is unavoidable for any differentially private mechanism.
Corresponds to CS/ECE 598DA, Weeks 3–4. Differential privacy is the guarantee that no single individual’s data materially changes a query’s output distribution, which is strong enough to resist the Dinur-Nissim- style attacks of privacy-attacks-and-motivations. Covers the standard mechanisms that achieve it — adding Laplace or Gaussian noise scaled to a query’s sensitivity, and the exponential mechanism for non-numeric outputs — and how privacy degrades predictably under composition (running several DP mechanisms on the same data), which is what makes DP usable as a budget to be spent across a whole analysis rather than a one-shot guarantee. The information-theoretic lower bounds half shows these mechanisms aren’t just convenient — a certain amount of noise/error is provably unavoidable for any mechanism meeting the DP definition, typically proved via tools from entropy-mutual-information (mutual information between the private data and the output).
Outline (TODO — flesh out each)
- The definition of differential privacy
- The Laplace mechanism
- The Gaussian mechanism
- The exponential mechanism
- Composition of differentially private mechanisms
- Information-theoretic lower bounds for differential privacy