Quasi-Identifier Set

Removing names, email addresses and account identifiers feels like anonymisation, and it is the control most teams apply. It fails for a reason that is easy to state and hard to design around: identification comes from combinations, not from fields. A postcode, a date of birth and a sex identify a large fraction of a population. A timestamped location trace identifies almost everyone. A search history identifies the person who wrote it.

The attributes that do this are quasi-identifiers. They are not secret, they are not labelled as personal, and there is no fixed list of them, because whether an attribute identifies someone depends on what else is in the dataset and what the attacker already knows.

Why it matters

The consequence is regulatory and architectural at once. Pseudonymised data is personal data: it reduces risk, and it does not remove obligations, permit unrestricted secondary use, or make a public release safe. Teams that believe otherwise build data flows — analytics exports, partner shares, model training sets — on a foundation that will not hold when examined.

The architectural consequence is that the control has to change. If identification lives in combinations, then the levers are aggregation, suppression, generalisation and linkage, not better identifier substitution. That is a different set of design moves, and it has to be decided before data is published rather than after.

Implementation patterns

• Enumerate the quasi-identifiers explicitly for any dataset leaving a trust boundary, and state the auxiliary data an attacker plausibly has. The assessment is only meaningful relative to that assumption.
• Generalise rather than remove: year of birth instead of date, region instead of postcode, hour instead of timestamp. This preserves analytical value where removal destroys it.
• Measure, do not assert. k-anonymity — every record indistinguishable from at least k-1 others on the quasi-identifiers — is a crude measure with known weaknesses, and it is far better than an opinion. Extensions such as l-diversity address the case where a k-anonymous group shares the same sensitive value.
• Break linkage. A persistent per-subject key is what assembles isolated observations into an identifying profile. Rotate it, or omit it where per-subject analysis is not required.
• Treat free text as unreleasable. It contains an unbounded set of quasi-identifiers and cannot be assessed field by field. Release categories and counts, not text.
• Attack it before release. Have someone attempt re-identification with realistic auxiliary data, and record the attempt. It is the only evidence that any of the above worked.

Industry example

AOL published roughly 20 million search queries from more than 650,000 users on 4 August 2006, replacing account names with random numbers. Within days the New York Times identified user 4417749 as a named individual from the content of her searches alone, and AOL's chief technology officer resigned later that month.

Two design lessons sit in that case. The substitution was irrelevant, because the identifying information was in the query text. And the persistent pseudonym actively caused the harm by stitching thousands of individually innocuous queries into one profile — the same queries, unlinked, would have been far less dangerous. The academic literature made the general point repeatedly around the same period, notably the 2008 de-anonymisation of a public film-rating dataset using a separate public film database as auxiliary data.

Failure scenarios

• "We hashed the identifiers." A hash of a stable key is a stable key, and the quasi-identifiers are untouched.
• Small cells. An aggregate that reports one person in a category discloses that person precisely, which is why suppression thresholds exist on statistical outputs.
• Auxiliary data appearing later. A release assessed as safe in 2019 becomes identifying when an unrelated dataset is published in 2023, and nothing can be done, because releases are irreversible.
• Linkage across releases. Two datasets each adequately generalised are joined on a shared quasi-identifier set, and the combination identifies people neither could alone.
• Free-text fields in a structured export — a notes column, a support ticket body — that were never assessed because the schema review looked at column names.
• Re-identification by an insider, who has far better auxiliary data than the external attacker the assessment assumed.

Trade-offs

Every mitigation costs analytical value, and the trade is real rather than rhetorical. Generalising a timestamp to the hour destroys sequence analysis; suppressing small cells removes exactly the rare groups researchers are studying; breaking linkage removes cohort analysis entirely. A privacy assessment that claims no utility was lost has usually not protected anything.

The honest framing is a choice between two failure modes: release something less useful, or release something identifying. Naming the analytical questions that survive each option, before deciding, is what turns this from an argument into a design decision.

When not to use it

Within a controlled environment — data that never leaves, access logged and contractual, purposes bound — the heavy machinery is disproportionate. Access control and purpose limitation deliver more protection per unit of effort, and generalising the data mainly degrades the analysis the environment exists to support.

The machinery earns its cost at the trust boundary, where output cannot be recalled: a public release, a partner share, a dataset used to train a model that will be distributed. Irreversibility is what makes a formal assessment necessary rather than a review.

Interview question

Q: A product team wants to publish an anonymised dataset of user journeys for a research partnership: user id hashed, timestamps to the second, city, device, and the free-text search terms entered. Tell me what you would change, what you would refuse, and how you would evidence that the result is defensible.

What a strong answer covers: identifying the quasi-identifier set rather than auditing for direct identifiers; refusing free text outright as unassessable; generalising timestamps and location, with the analytical cost stated; removing or rotating the per-user key because linkage is what builds the identifying profile; a measurable criterion such as k-anonymity with its known limitations acknowledged; an adversarial re-identification attempt with realistic auxiliary data as the evidence; and the recognition that release is irreversible, so a controlled research environment may be the better answer to the same request.

Quick check

Quiz: Why did hashing the user identifier not protect AOL's search data? — The identifier was never the identifying information; the query text was. Worse, a stable key linked thousands of individually harmless queries into a single profile, which is what made identification possible.

Flashcard: What are the four levers against quasi-identifiers? — Aggregation, suppression, generalisation and breaking linkage. Better identifier substitution is not among them, because the identifiers were not the vector.