k-anonymity, explained with a hospital waiting room

Picture a hospital waiting room. Twelve people are sitting in it. A stranger walks in holding a sheet of paper that lists, for one patient: female, born March 1961, lives in postcode 2041, treated for bladder pain. No name. No photo.

If only one woman in the room matches that description, the sheet of paper was never anonymous. It was a name written in different ink.

That is the entire problem k-anonymity exists to solve — and the waiting-room test is still the fastest way to reason about it.

What k-anonymity actually says

k-anonymity is a property of a released dataset, not a promise about it. A release is k-anonymous when every record is indistinguishable from at least k − 1 other records on its quasi-identifiers — the ordinary fields an outsider could plausibly know about you: ZIP code, birth date, sex, admission month, broad diagnosis.

The definition comes from Latanya Sweeney's 2002 paper, and it is worth quoting, because the original is clearer than most paraphrases:

A release provides k-anonymity protection if the information for each person contained in the release cannot be distinguished from at least k − 1 individuals whose information also appears in the release.

In the waiting room: if the stranger's sheet matches five people instead of one, the best the stranger can do is a one-in-five guess. The group is the protection. k is the size of the group.

Why the name column was never the problem

The counterintuitive part — and the reason this idea needed inventing — is that removing names barely helps. Sweeney demonstrated this the hard way in the 1990s: using only ZIP code, birth date, and sex, she re-identified the medical record of the sitting governor of Massachusetts in a dataset the state had released as "anonymized," and later estimated that 87% of Americans are uniquely identified by those three fields alone.

Three ordinary fields. No names, no Social Security numbers, no addresses. The combination is the identifier.

This is why modern privacy law refuses to treat "we deleted the name column" as anonymization. The HHS de-identification guidance under HIPAA spells out eighteen identifier classes precisely because re-identification happens through combinations — and GDPR's Recital 26 asks whether a person is identifiable by "all the means reasonably likely to be used," not whether a label was removed. We cover how those regimes differ in de-identified, anonymized, pseudonymized: what these words actually mean.

Where k = 5 comes from

There is nothing magical about five. It is where decades of health-statistics practice landed.

Long before k-anonymity had a name, public-health agencies enforced minimum cell sizes in published tables: if a count described fewer than some threshold of people, the cell was suppressed. CMS data-use agreements prohibit publishing cells under 11; many U.S. state health departments and European statistics offices use 5 or 10. The instinct is identical to Sweeney's formalism — small groups identify people — and we trace that lineage in why small numbers are dangerous.

A floor of k ≥ 5 caps any linkage guess at a one-in-five confidence — the permissive end of the common 5–11 suppression range (CMS requires 11) — chosen because it holds the line while leaving research-grade utility intact. The question that matters is not "why five?" — it is "what happens at four?" In most systems, the answer is a judgment call by whoever is running the query. In a well-built system, the answer is: the release does not happen.

What k-anonymity cannot do

k-anonymity has known failure modes, and pretending otherwise is how "anonymized" datasets end up in the news.

None of these break the idea; they bound it. k-anonymity defends one front — linkage through quasi-identifiers — and it must be one layer in a stack that also includes consent, access control, audit, and aggregate-only query patterns. The re-identification literature is a catalog of what happens when a single layer is asked to do the whole job; we walk through the famous cases in re-identification attacks.

A floor, not a dial

Here is the test that separates privacy apparatus from privacy policy: who can change the number?

If k is a configuration value — a row in a settings table, a flag a sufficiently senior person can override for a sufficiently important study — then the protection is organizational, and organizations have bad quarters. If k is structural — enforced in the release path itself, with refusals logged on the same audit spine as everything else — then the protection holds precisely on the day someone is motivated to bend it.

That is how we build it at Mithras Health: cohorts are assembled over consented records, and below k = 5 the gate refuses to release — for everyone, for every study, with the refusal recorded in an append-only audit trail. Not because a regulation names the number five, but because a floor you can lower is a floor in name only.

The waiting room is a useful place to end, too. The promise k-anonymity makes is modest and honest: whatever a stranger learns, they learn about a group, never about you alone. Modest, honest promises — enforced by machinery rather than goodwill — are the only kind worth making about health data.