Re-identification of anonymized data

Why can a dataset with every name removed still reveal exactly who is in it?

The intuition behind anonymization is that identity lives in a column. Names, national insurance numbers, email addresses: strike them out and the people dissolve into rows. It feels like removing the label from a jar.

But ask what "identifying" actually means. It means narrowing a population down to one person. A name does that well because names happen to be nearly unique. Nothing in that definition says a name is the only thing that does it — and once you notice that, the interesting question becomes not which columns are identifiers, but how many people are left standing after you have applied all the columns you kept.

Count. Every attribute you retain multiplies the number of distinguishable combinations. A full date of birth splits a population about thirty-six thousand ways over a century. Multiply by two for sex. Multiply by the tens of thousands of postal codes in a country. The number of possible cells now vastly exceeds the number of people, so most cells hold nobody and most of the occupied ones hold exactly one person. The population is not being described; it is being enumerated.

This was measured. Latanya Sweeney's much-cited estimate from 1990 census data was that around 87% of the United States population was uniquely identified by the combination of five-digit ZIP code, sex and full date of birth. Philippe Golle later redid the calculation on the 2000 census and got about 63%. The gap between those figures is worth keeping in view — the effect is large under either, but the precise magnitude is a genuine methodological dispute, not a settled constant.

Uniqueness alone, though, still names nobody. A row that describes exactly one person does not tell you which person. So what is the second ingredient? An outside dataset that contains both the identity and some of the same attributes. Sweeney demonstrated this by buying a state voter roll for a nominal sum, joining it on ZIP, sex and birth date to a supposedly de-identified set of state employee hospital records, and pulling out the governor's medical file. Re-identification is a join, and the joining key is assembled from columns nobody had classified as a key at all. That is the whole trick: proxy evidence.

Now push it further. What happens with data that is not demographic but behavioural — what you watched, where your phone was, what you bought? Such data is high-dimensional and sparse: thousands of possible values, each person touching only a few. Narayanan and Shmatikov showed on the released Netflix Prize ratings that eight movie ratings with their dates — allowing two of the eight to be wrong and the dates to be off by up to a fortnight — picked out 99% of records uniquely, and demonstrated the linkage against public IMDb reviews. Behaviour is a fingerprint, and a coarse, error-tolerant one at that.

The obvious response is to generalise until nobody is unique: age bands instead of birth dates, regions instead of postcodes, until every combination of quasi-identifiers is shared by at least k people. That is k-anonymity, and its failure is instructive. If all k records in a group share the same diagnosis, you have learned the diagnosis without ever identifying the row — so l-diversity was proposed to force variety within a group, then t-closeness after that. Each patch answered one attack and was followed by another.

Is there a bottom to this? There is, and it is not about columns at all. Dinur and Nissim showed that if you answer enough statistical queries about a database accurately enough, an adversary can reconstruct the underlying records — whatever you deleted first. The obstacle is not a bad list of identifiers; it is that utility and privacy trade against each other quantitatively, and that trade must be paid in noise rather than in redaction.

The correction worth making is this: "anonymized" is not a property of a dataset. It is a relation between the dataset and everything else in the world, and it can quietly stop holding after publication, when a new auxiliary source appears. A dataset released as safe in 2010 may be trivially linkable in 2030 without a single byte of it having changed.

It follows that "quasi-identifier" cannot be a fixed list. Any attribute is a quasi-identifier if some accessible dataset contains both it and a name. Postcode qualifies today because voter rolls and marketing files are cheap; step count and typing rhythm qualify to whatever extent someone has published them next to identities.

Two honest caveats. First, how often re-identification actually happens in the wild is contested. Critics of the alarming reading — Khaled El Emam and colleagues among them — point out that most celebrated attacks targeted data that was poorly de-identified by the standards of formal statistical disclosure control, and that measured re-identification rates on properly treated data are low. The counter-argument is that a shortage of published attacks is not evidence of safety, and that an attacker's stock of auxiliary data only ever grows. Both positions are held by serious people. Second, the formal answer — differential privacy, which bounds how much any one person's presence can change a released statistic — is itself contentious in application: the United States Census Bureau's adoption of it for the 2020 data drew sustained objections from demographers who argued the injected noise damaged small-area analysis. Buying privacy with noise is a real cost, not a free upgrade.

• How differential privacy converts the question from "which columns" to "how much noise", and what it costs.
• Why synthetic data inherits the same problem when the generator was fitted too closely to real records.

Every term the collection defines is gathered in the glossary.