The Core Intuition: Plausible Deniability
Imagine you want to know what percentage of employees at a company have a certain medical condition. If you ask each employee directly, they may lie to protect their privacy. But if you tell each employee: "Flip a coin privately. If heads, answer truthfully. If tails, answer 'Yes' regardless" — then you can statistically correct for the coin flips and get an accurate aggregate, while each individual has plausible deniability ("I might have just flipped tails").
Differential Privacy (DP) formalizes this intuition mathematically. An algorithm is differentially private if its output distribution is nearly identical whether or not any single individual's record is included in the input dataset.
Formally: for any two datasets D and D' that differ by exactly one record, and for any possible output S:
P[M(D) ∈ S] ≤ e^ε × P[M(D') ∈ S]
Where M is the algorithm (mechanism) and ε (epsilon) is the privacy budget. This means an attacker who sees the output cannot determine with confidence whether your record was in the dataset — your participation is mathematically deniable.
Epsilon (ε): The Privacy Budget
Epsilon is the single most important parameter in Differential Privacy. It controls the privacy-utility trade-off:
| Epsilon (ε) | Noise Level | Privacy | Accuracy | Typical Use Case |
|---|---|---|---|---|
| 0.01 – 0.1 | Very high | Very strong | Low | Highly sensitive medical data |
| 0.5 – 1.0 | Moderate | Strong | Moderate | Census data, health surveys |
| 5 – 10 | Low | Weak | High | Internal analytics, low-risk data |
| > 10 | Negligible | Minimal | Very high | Effectively no DP protection |
Privacy budget composition: Every query against a DP system consumes some of the budget. If you run 100 queries each costing ε=0.1, the total privacy loss is ε=10. This is why DP systems track cumulative budget consumption — once the budget is exhausted, no more queries are permitted without resetting (which typically means collecting new data).
The Laplace Mechanism
The most common DP implementation adds Laplace-distributed noise to numerical query results. The noise scale is calibrated to the sensitivity of the query (how much one person's record can change the result) divided by epsilon:
Noise ~ Laplace(0, sensitivity/ε)
For a query "What is the average salary?" with sensitivity $50,000 (the maximum one person could shift the average) and ε=1.0, the mechanism adds random noise drawn from Laplace(0, 50000). The true average might be $72,000; the released result might be $68,400 or $75,200.
Real-World Deployments
Apple (iOS): Uses Local Differential Privacy to collect keyboard usage statistics, emoji frequency, and health data. Noise is added on-device before transmission — Apple's servers never see raw individual data.
Google (RAPPOR): Uses Local DP to collect Chrome browser statistics (default search engines, homepage settings) from hundreds of millions of users.
US Census Bureau: Applied DP to the 2020 US Census to protect individual responses while still publishing accurate aggregate statistics at the national level.
Google's Privacy Sandbox: Uses DP-based techniques (like the Topics API) to enable ad targeting without exposing individual browsing histories to advertisers.