Proving One Person’s Answer Could Not Have Changed the Result
Core Concept
Every older privacy idea tried to scrub the data \u2014 strip the names, bucket the ages, k-anonymise the rows. All of them failed the same way: an attacker who joins your "anonymous" release against any other dataset re-identifies people.
Two verified results show why. Sweeney (2000) found 87% of the US population were likely unique on just {5-digit ZIP, gender, date of birth} and 53% on {city, gender, date of birth}. Narayanan & Shmatikov re-identified Netflix Prize users by joining the "anonymous" ratings against IMDb's public data. Scrubbing the data never works, because the data is still joinable.
Differential privacy abandons that framing and makes a claim about the algorithm instead: a randomised mechanism is private if its output distribution is almost the same whether or not YOUR record is in the input.
Key Components
\u03b5-differential privacy
Two datasets differing in one person produce statistically indistinguishable outputs. The bound is e^\u03b5 on any outcome's probability \u2014 it protects one person in the data, not the file.
Epsilon = a privacy budget
Small \u03b5 \u2192 more noise \u2192 a stronger promise. The budget composes: every query spends some of it, so real systems cap total queries rather than noising each one in isolation.
Noise scaled to sensitivity
Add Laplace or Gaussian noise scaled to the query's sensitivity (how much one person can move the answer). A count has sensitivity 1; a sum over unbounded values has huge sensitivity \u2014 clip first or the answer is unusable.
Central vs Local DP
Central: a trusted collector adds the noise. Local: randomise on the device (randomised response) \u2014 no trusted party, but it costs far more accuracy.
How It Works
- Don't scrub the data. The goal is to publish answers, not a cleaned copy \u2014 the data stays joinable, so the protection must live in the release.
- Pick a query and measure its sensitivity. How much can a single person's record move the answer? A count moves by 1; a mean or sum can move a lot.
- Sample noise scaled to sensitivity \u00f7 \u03b5. Laplace for the classic bound, Gaussian when you want a normal-looking output.
- Add the noise and publish the perturbed value. It's close to the truth in aggregate, but the exact value can't be pinned to one person.
- Account the spend. Every release burns part of the \u03b5 budget; track the running total so the whole publication, not one query, stays within the promise.
Real-World Applications
- Not anonymisation, not encryption. It constrains what your outputs reveal, not the raw dataset you still hold \u2014 it is no substitute for access control.
- The Laplace is not Laplace smoothing. Smoothing adds one to a count so no probability is zero \u2014 same name, a different job.
- This \u03b5 is not the robustness \u03b5. An attack-budget \u03b5 bounds a pixel perturbation; this privacy-budget \u03b5 bounds one person's influence on the answer.