Re-identification attacks: how 'anonymous' health data gets unmasked

In the spring of 1996, the governor of Massachusetts collapsed at a public ceremony and was taken to the hospital. The story led the evening news. Not long after, an MIT graduate student named Latanya Sweeney paid twenty dollars for the Cambridge voter roll, joined it against a state insurance dataset that had been released to researchers with names removed, and pulled out Governor William Weld's hospital record.

Then she mailed it to his office.

The state had not been reckless by the standards of the day. Names, addresses, and Social Security numbers were gone. What remained — ZIP code, birth date, sex — looked harmless. But the voter roll carried the same three fields, plus names. Six people in Cambridge shared the governor's birth date. Three were men. One lived in his ZIP code.

Every famous unmasking since has been a remix of that afternoon.

Every attack is the same attack

Strip away the details and almost every re-identification of "anonymous" data is one move: a linkage attack. Take the released dataset. Find a second dataset that overlaps with it on a few fields and still carries names. Join the two. Wherever the join lands on exactly one person, the anonymity is gone.

The overlapping fields are the quasi-identifiers — ordinary attributes nobody thinks of as identifying. ZIP code. Birth date. Sex. Admission month. The five movies you rated last Tuesday. Individually common; in combination, nearly unique. Sweeney later quantified the intuition: by her estimate, 87% of Americans are uniquely identified by ZIP code, birth date, and sex alone.

The defender's mistake is always the same, too: judging the release in isolation. A dataset is never anonymous in a vacuum. It is anonymous relative to what else exists — and the publisher does not control what else exists.

Four unmaskings worth knowing

The well-known cases differ in costume, not in plot. Each time, an auxiliary dataset existed that the publisher had not accounted for.

The AOL case removed user names and substituted numeric IDs — but the queries were the identifier. People search for their own names, their streets, their doctors. The Netflix case is subtler and more instructive: researchers Arvind Narayanan and Vitaly Shmatikov showed that a handful of movie ratings with rough dates is enough to match an "anonymous" Netflix subscriber to their public IMDb reviews, because high-dimensional data is sparse — almost every record is unique in some small set of coordinates.

Strava is the modern coda. The heatmap was aggregated GPS data from millions of athletes, which sounds safe — until you look at a desert region where the only people wearing fitness trackers are soldiers jogging the perimeter of a base that does not appear on maps. Aggregation protects only where crowds exist. That is the same lesson health statisticians learned decades ago about small counts, and it is why small-cell suppression exists.

Why removing names keeps failing

Names were never the identifier. The combination is — and in rich data, nearly every record is a combination of one.

A health record is high-dimensional by nature: diagnosis codes, dates of service, medications, procedures, providers. A rare condition plus an admission week plus an age band can narrow a county-sized population to a single bed. This is why "we deleted the name column" has never satisfied serious privacy law. The HHS de-identification guidance defines two formal paths — Safe Harbor's eighteen identifier classes or an expert's documented risk analysis, compared in our Safe Harbor vs. Expert Determination explainer — precisely because identification happens through combinations. GDPR's Recital 26 goes further and asks whether a person is identifiable by "all the means reasonably likely to be used," by anyone, not just the publisher. The three legal vocabularies — de-identified, anonymized, pseudonymized — carve up this territory differently, and the differences matter.

Assume the second dataset exists

The only safe design assumption is that the attacker already holds auxiliary data. A defense premised on its absence is not a defense; it is a bet.

In 1997 the auxiliary dataset was a voter roll that cost twenty dollars. Today, data brokers sell location traces, purchase histories, and app telemetry at scale — an entire economy of linkable data that no publisher can enumerate. Defenses that survive this assumption share a shape:

• Group floors. Never release anything that describes a group smaller than k people, so a perfect linkage still yields only a one-in-k guess. That is k-anonymity, and it works precisely because it does not care what the attacker knows.
• Aggregates, not records. A count cannot be joined row-by-row. Releasing statistics instead of microdata removes the linkage surface — provided the counts themselves stay above the floor.
• Conservative quasi-identifier lists. Treat any field an outsider could plausibly learn as identifying, including ones that feel innocent today.
• Audited cumulative disclosure. Two releases, each safe alone, can intersect to a group of one. Someone has to be keeping the ledger.

None of these make re-identification impossible. They make it bounded, priced, and visible — which is what engineering, as opposed to hoping, looks like.

The bar a release has to clear

At Mithras Health we treat Sweeney's voter roll as a permanent fixture of the threat model: for every release, we assume the linking dataset is already on someone's desk. Research queries on the platform are federated and return aggregates only — no row-level data leaves custody — and every result must clear a hard k ≥ 5 floor. A cohort smaller than five people is not released, for anyone, for any study; the refusal itself is recorded in an append-only audit trail. The floor is not a setting, because a floor that someone can lower under deadline pressure is exactly the kind of defense the last thirty years have been refuting.

The Weld story is usually told as a gotcha. The better reading is humility. The state's privacy officers were not fools; they simply could not enumerate every dataset in the world, and neither can anyone now. "Is this data anonymous?" is the wrong question. The right one is: anonymous against whom, holding what, for how long? Build for the worst honest answer, and the twenty-dollar voter roll loses its power.