In 1997 a graduate student named Latanya Sweeney bought a Massachusetts voter roll for twenty dollars. She joined it against a "de-identified" hospital insurance release — names removed, everything else intact — on three columns: ZIP code, date of birth, sex.
She found the Governor's medical record. Then she mailed it to him.
No cryptography was broken. No rule was violated. It was a JOIN.
I built the whole thing from scratch in a browser tab: the attack, k-anonymity, the attack that walks past k-anonymity, and then the only thing that survived — with every distribution sampled hundreds of thousands of times and checked against its closed form.
👉 Live, everything computed in your browser: https://dev48v.infy.uk/ai/days/day61-differential-privacy.html
The attack is nine lines
groups = defaultdict(list)
for row in released_medical_data:
groups[(row.zip, row.dob, row.sex)].append(row) # nothing sensitive here
for person in public_voter_roll: # you can buy this
hits = groups[(person.zip, person.dob, person.sex)]
if len(hits) == 1:
print(person.name, "has", hits[0].diagnosis) # done.
On my synthetic 600-record release: 98.7 % of rows have a unique quasi-identifier, and the join names 197 of the 200 people in the attacker's list, diagnosis attached.
Sweeney's number for the real US population was ~87 %. Netflix published anonymised ratings for a competition and researchers de-anonymised subscribers against public IMDb reviews. AOL published anonymised search logs and a newspaper found a named user within days.
None of these were sloppy by the standards of the time. They were all anonymised in the way that word is normally used. The failure is structural. Whether a release identifies you depends on what the attacker already knows — and you cannot enumerate that set, let alone bound it.
Why every patch failed
The obvious repair is k-anonymity: generalise until every quasi-identifier group holds at least k people. It works. It stops naming.
It does nothing about the sensitive column:
("021**", "1965-19xx", "F", "HIV")
("021**", "1965-19xx", "F", "HIV")
("021**", "1965-19xx", "F", "HIV")
k = 3. Nobody is named. And if you can place Alice in that group you now know her diagnosis with certainty. That is the homogeneity attack, and my page counts it as a separate column from "named" because it is a separate failure — on the raw release it leaks 197 diagnoses via naming, and it keeps leaking diagnoses at generalisation levels where naming has already stopped.
l-diversity patched homogeneity. t-closeness patched l-diversity. Each fell to an attacker with better background knowledge.
Underneath all of it sits Dinur–Nissim (2003): answer enough subset-sum queries too accurately and the entire database can be reconstructed. That is a theorem, not a warning about a bad release. Accuracy and privacy were never independent knobs.
The US Census Bureau proved it on itself in 2018 — it reconstructed 245 million individual records from its own published 2010 tables.
The definition
Differential privacy changes what the guarantee is about. It stops being a property of a dataset and becomes a property of the mechanism.
A randomised mechanism M is ε-differentially private if for every pair of databases D, D′ differing in one person, and every set of outputs S:
Pr[M(D) ∈ S] ≤ e^ε · Pr[M(D′) ∈ S]
Read it as a promise made to you personally: whatever anyone concludes from the output, they would have concluded almost exactly the same thing had your row never existed.
Three things follow, and they are why this definition survived where the others did not:
- It holds against any adversary with any auxiliary information, present or future — the bound is on the algorithm and never mentions the attacker.
- It cannot be broken by a dataset someone publishes next year.
- It composes, so you can reason about many releases at once.
One clarification worth internalising: DP does not promise you learn nothing about the world. If a DP study establishes that smoking causes cancer and you are a known smoker, your insurer learns something — but it would have learned it whether or not you participated. DP protects your participation, which is the only thing you actually control.
What ε means, in a number you can feel
The inequality is hard to feel. So convert it into the only question a person cares about: can someone tell whether I was in the dataset?
Give an adversary a 50/50 prior, one output, unlimited computation and every auxiliary dataset in existence. Their best possible strategy is the likelihood-ratio test, and ε-DP caps their success probability at exactly e^ε/(1+e^ε):
| ε | adversary's best accuracy |
|---|---|
| 0.1 | 52.5 % — a coin |
| 1 | 73.1 % |
| 3 | 95.3 % |
| 5 | 99.3 % — not a guarantee |
My page runs that adversary for real. At ε = 1 it measured 69.4 % against a cap of 73.1 % — always below, because the cap is the worst case over all possible outputs while a real attacker lives with the ones that actually occur. The bound is a promise about the worst day, not a prediction of the average one.
Sensitivity, and the trap in every sum
You cannot add noise until you know how much one person can matter:
Δf = max |f(D) − f(D′)| over all neighbouring pairs
A count is Δf = 1 — a person is either in or out.
A sum over an unbounded column is infinite — one billionaire moves the total arbitrarily far — so no finite noise makes it private. You must clip first, and the clip bound then is the sensitivity.
That clip is not a preprocessing convenience, it is the privacy parameter. In my lab, switching the query from a count to a clipped sum moves the sensitivity from 1 to $60,000 and the typical error from ±1 person to ±$2.3 million. That is the honest price of a query one person can move a long way.
And choosing the clip by looking at the data (say, the 99th percentile) leaks information unless you pay for that look out of the same budget. It is a real and common leak.
There is also a free win: in a histogram over disjoint buckets, one person lands in exactly one bucket, so the whole histogram costs ε, not ε per bucket. Parallel composition.
The Laplace mechanism, and why that shape
Add Laplace(Δf/ε). The proof is one line and worth doing once, because it explains the choice of distribution:
P_D(x)/P_D′(x) = exp( (|x−a′| − |x−a|)/b )
≤ exp( |a−a′|/b )
≤ exp( Δf/b ) = e^ε when b = Δf/ε
Nothing about the double exponential is aesthetic. It is the distribution whose log-density is piecewise linear, which is exactly what makes the ratio bounded everywhere rather than growing in the tail.
def laplace(b, u): # u ~ Uniform(-0.5, 0.5)
return -b * sign(u) * log(1 - 2*abs(u))
One production warning: naive floating-point Laplace sampling is attackable — the irregular gaps in the float grid leak information about the exact noise drawn (Mironov, 2012). Real libraries use discrete Laplace or a snapping mechanism.
The part I am proudest of: measuring ε instead of quoting it
Every DP tutorial states the guarantee. I wanted to see it.
So: draw 60,000 outputs from M(D) and 60,000 from M(D′), bin them, and take the largest |log ratio| over bins both distributions reach. At ε = 1 that came out 1.080.
Which is above 1. Is the mechanism broken?
No — and this is the trap. That estimator is biased upward, because you are taking a maximum over many noisy ratios. So I added a null control: run the identical estimator on two independent samples from the same distribution, where the true privacy loss is exactly zero.
measured = max_log_ratio(sample_from_D, sample_from_D_prime) # ~ eps
floor = max_log_ratio(sample_from_D, ANOTHER_sample_from_D) # TRUE answer is 0
The floor measured 0.078. So 1.080 is 1.00 plus instrument noise, and the two agree.
Drop to ε = 0.1 and it gets more interesting: measured 0.162, floor 0.092. The noise of the instrument is now the same size as the effect being measured. That is not a flaw in the page — it is why real privacy audits report lower bounds on ε and never certificates. An audit can find a bug. It cannot certify a guarantee.
If you write an empirical privacy check without a null control, you do not know what your numbers mean.
δ, and where the Gaussian bound actually breaks
Gaussian noise cannot give pure ε-DP. Its log-density is quadratic, so the log-ratio grows without bound in the tail and no finite ε covers every output. δ is the probability that the guarantee simply does not apply.
σ = Δf · sqrt(2 ln(1.25/δ)) / ε # requires ε ≤ 1
Under D the privacy loss is exactly Normal, so the tail probability has a closed form you can evaluate rather than trust:
assert loss_tail(1, eps=1.0, delta=1e-5) <= 1e-5 # 1.06e-6 ✅
assert loss_tail(1, eps=8.0, delta=1e-5) > 1e-5 # 2.92e-5 BREAKS
I assert the failure at ε = 8 deliberately, to show the ε ≤ 1 condition is load-bearing rather than decorative. People ship guarantees they do not have by ignoring it.
Second warning: δ must sit far below 1/n. At δ = 1/n, a "mechanism" that picks one person uniformly at random and publishes their entire record in the clear satisfies the definition.
ε is a budget you spend
Two ε-DP answers to the same question can be averaged by an attacker, so the pair is 2ε-DP. That is sequential composition, and it means a DP database contains a finite number of questions rather than a rate limit.
Advanced composition does better for many queries by accepting a small failure probability:
basic = k·ε
advanced = sqrt(2k·ln(1/δ′))·ε + k·ε·(e^ε − 1)
Note carefully: advanced is worse than basic for small k. An accountant that always reaches for it is throwing budget away. Take min(basic, advanced).
At ε = 0.2 per query, 200 queries:
| accounting | total ε |
|---|---|
| basic | 40.00 |
| advanced (δ′ = 1e-5) | 22.43 |
| measured 99.9th percentile | 11.91 |
Both bounds are conservative by a wide margin, because a bound is a worst case over outputs while a real run sees typical ones. Closing that gap is exactly what Rényi-DP, zCDP and the moments accountant do — and it is the technical reason DP-SGD became practical rather than theoretical.
And the tempting bug, which is a total leak: "the noise is fresh each time, so re-running is free." No. Averaging k noisy answers kills the noise like 1/√k.
Post-processing immunity
Any function of a DP output is DP with the same ε. No conditions, no exceptions. The proof is one sentence: if no test can distinguish M(D) from M(D′), no function of them can either — such a function would itself be a test.
This is the property that lets DP scale. Round it, clip it, plot it, train on it, hand it to an adversary with a supercomputer — the guarantee is unchanged. Compare k-anonymity, where merging two separately k-anonymous releases can produce a re-identifiable one, so every downstream consumer becomes part of your threat model.
The one rule: post-process the output, never re-touch the raw data.
if abs(noisy - true_count(D)) > 100: # <-- read the raw data
noisy = dp_count(D, pred, eps) # budget spent, guarantee void
That looks completely reasonable in a code review. It is the single most common way real DP deployments leak.
The utility arithmetic, in one line
relative error = (1/ε) / count
A DP count has expected error 1/ε regardless of n. So at ε = 1:
- count of 30,000,000 → ±1 → 0.000003 % — free
- count of 30,000 → ±1 → 0.003 % — fine
- count of 30 → ±1 → 3 % — painful
- count of 3 → ±1 → 33 % — useless
DP is essentially free on large populations and often impossible on small ones. Small subgroups pay the entire cost, which is a real equity problem rather than a rounding error — the loudest objections to the Census Bureau's DP redistricting data came from researchers studying small rural and tribal populations, whose counts are exactly the ones the noise swamps.
Local DP: Warner beat the theory by 44 years
Everything above assumes a trusted curator holding raw data. Local DP removes that: each person randomises their own answer before it leaves the device, so a breach of the server reveals nothing.
Randomised response — invented by Warner in 1965 for surveys about embarrassing behaviour, decades before the definition it satisfies was written down:
def randomised_response(true_bit, p, rng):
return true_bit if rng.random() < p else not true_bit
eps = log(p / (1 - p))
estimate = (observed_yes_fraction - (1 - p)) / (2*p - 1) # exactly unbiased
At p = 0.70 (ε = 0.847), my 20,000-person simulation: true rate 37.05 %, raw tally 43.4 % (biased toward 50/50), debiased estimate 36.80 % ± 0.71 points.
No single answer is evidence of anything — anyone can always say "the coin made me." Plausible deniability is a theorem here, not a slogan.
The cost is severe: local-model error grows like √n instead of staying constant, so you need orders of magnitude more users. The shuffle model — local noise plus anonymised delivery — is the modern middle ground.
How to read a published ε
DP-SGD is the same recipe applied to gradients: clip each example's gradient (that clip is the sensitivity), add Gaussian noise to the batch sum, track the budget with an RDP accountant.
The numbers that shipped:
- US Census 2020 redistricting: ε ≈ 19.61 — per person, whole release
- Apple telemetry: ε 2–16 — per feature, per day
- most academic work: ε ≤ 1
Those are not comparable, and treating them as one scale is the commonest way to be misled. ε is only defined relative to a unit of privacy and a neighbouring relation. So the first question about any published ε is always ε per *what*? One person? One record? One device-day? One training example?
An impressively small ε on a badly chosen unit protects nobody. That is where most of the real argument in deployed DP now lives.
Verification
The page ships with its maths block extracted verbatim and run in Node against independent baselines: both samplers against their analytic CDFs by a Kolmogorov–Smirnov statistic, the noise scales against their closed forms, sensitivities by brute force over real neighbouring databases, the Gaussian tail against its exact expression, composition against measured totals, and the re-identification counts against a from-scratch recount. 433 assertions, all passing, plus 140 more that run in your browser while you read.
If you take one thing from this: stop saying "anonymised". It is not a property the data can have. Ask what mechanism produced the release, what its ε is, and what that ε is per.
Live page: https://dev48v.infy.uk/ai/days/day61-differential-privacy.html
Repo: https://github.com/dev48v/ai-from-zero
Top comments (0)