Differential Privacy

framework · mathematics · formal-scientific

Formal definition guaranteeing that the inclusion or exclusion of any single record does not significantly affect query outputs.

Differential Privacy is a formal mathematical framework for privacy-preserving data analysis, providing a precise definition of privacy that can be quantified, composed across queries, and operationally guaranteed by appropriate algorithms. The framework was articulated by Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith in their 2006 paper 'Calibrating Noise to Sensitivity in Private Data Analysis' (Dwork's 2006 'Differential Privacy' paper provides the canonical definition). The formal definition: a randomized algorithm M is ε-differentially private if for any two datasets D and D' differing in a single record, and for any subset S of possible outputs, P[M(D) ∈ S] ≤ exp(ε) × P[M(D') ∈ S]. This means the algorithm's output distribution changes only slightly when any single individual's record is added or removed, providing a strong privacy guarantee independent of attacker prior knowledge. The parameter ε quantifies the privacy-utility tradeoff: smaller ε means stronger privacy but typically less accuracy. Mechanisms achieving differential privacy include: Laplace mechanism (add Laplace noise scaled to query sensitivity); Gaussian mechanism (Gaussian noise, with relaxed (ε,δ)-DP definition); exponential mechanism (for non-numeric outputs); subsampling and shuffle amplification; private machine learning via DP-SGD (Abadi et al. 2016). Applications include the US Census Bureau's adoption of differential privacy for the 2020 Census, Apple's deployment in iOS for telemetry collection, Google's RAPPOR system for Chrome telemetry, and substantial regulatory interest. The framework provides genuine technical guarantees but with substantial practical complexity in choosing ε, calibrating noise to sensitivity, and managing the privacy budget across multiple queries.

Originators

Cynthia Dwork; Frank McSherry; Kobbi Nissim; Adam Smith high

Year / Decade

2006 (foundational papers); 2014 (Dwork-Roth Algorithmic Foundations of Differential Privacy); ongoing development high

Primary sources

Dwork, C., McSherry, F., Nissim, K. & Smith, A. (2006). 'Calibrating Noise to Sensitivity in Private Data Analysis', TCC, Dwork, C. (2006). 'Differential Privacy', ICALP, Dwork, C. & Roth, A. (2014). 'The Algorithmic Foundations of Differential Privacy', Abadi, M. et al. (2016). 'Deep Learning with Differential Privacy', CCS high

Core components

Formal ε-differential privacy definition: P[M(D) ∈ S] ≤ exp(ε) × P[M(D') ∈ S] for neighboring datasets
(ε,δ)-DP relaxation
Privacy budget ε quantifying privacy-utility tradeoff
Composition theorems (sequential composition, parallel composition, advanced composition)
Laplace and Gaussian noise mechanisms
Exponential mechanism for non-numeric outputs
Sensitivity analysis of queries
DP-SGD for private machine learning (Abadi et al. 2016)
Local vs central differential privacy
Substantial industry deployment (US Census, Apple, Google)

Primary use case

Privacy-preserving data analysis particularly for sensitive personal data; US Census Bureau deployment for 2020 Census disclosure avoidance; Apple iOS telemetry collection; Google's RAPPOR system; private machine learning (DP-SGD); regulatory frameworks responding to privacy concerns (GDPR, state privacy laws); foundation for substantial commercial 'privacy tech' tools and services; reference framework in privacy-preserving computation research.

Common criticisms

Choosing the privacy parameter ε is genuinely difficult and contested — there is no clear principled basis for selecting specific ε values, and the same ε can mean substantially different operational privacy in different contexts
small ε (strong privacy) often produces substantial utility loss
the privacy budget ε accumulates across queries, requiring careful management that is operationally complex
the formal guarantee is for a single dataset definition that may not match how attackers actually query
local differential privacy (where individuals add noise locally before sending data) has weaker privacy-utility tradeoffs than central DP
commercial 'differential privacy' implementations vary substantially in fidelity to the formal definition and in noise calibration quality
the framework is often misunderstood — including by some implementers — as providing privacy 'in general' rather than the specific neighboring-dataset guarantee
recent attacks (Carlini et al. on language model memorization) have raised questions about whether DP-SGD privacy guarantees translate to operational privacy in deep learning
the US Census Bureau's 2020 deployment generated substantial controversy about utility loss for downstream uses.

Lineage

Siblings: Information Theory