Module 4 · 7 min read
De-identification, anonymisation and the re-identification gap
Why stripping identifiers does not produce anonymous data, what k-anonymity guarantees and what it misses, and how to reason about re-identification risk.
A pipeline strips names, email addresses and account numbers from records before they enter a training corpus. The team updates the data classification to anonymous, and with that stroke removes the dataset from the scope of its retention schedule, its access controls and its impact assessment. This is one of the most consequential mislabellings in practice, and it is wrong for a specific technical reason: direct identifiers are not the only link back to a person.
What remains after the strip is a set of quasi-identifiers: postcode, date of birth or age band, sex, job title, employer, admission month, device model, the timestamp pattern of activity. Individually they identify nobody. In combination, and especially in combination with any external dataset an adversary can obtain, they routinely single out individuals. Rare attribute combinations do most of the work: an unusual job title in a small postcode, or a single record with an extreme value, is often unique in the population. Because the records remain linkable to a person by means reasonably likely to be used, they remain personal data, and the correct label is de-identified or pseudonymised.
- Direct identifier
- A field that names a person on its own: full name, email address, national identifier, account number.
- Quasi-identifier
- A field that does not identify anyone alone but does so in combination with other fields or with an external dataset.
- Pseudonymisation
- Replacing identifiers with a token or hash so that re-identification requires additional information. The data remains personal data.
- Anonymisation
- An outcome, not a technique: re-identification is not reasonably possible for anyone, taking account of all means reasonably likely to be used, including linkage with other available data.
De-identified or pseudonymised
- Direct identifiers removed, replaced or hashed
- Quasi-identifiers remain and stay linkable
- Re-identification possible with additional information
- Still personal data: retention, access control and subject rights all still apply
- A useful risk-reduction measure, and a weighting factor in a compatibility assessment
Anonymised
- An outcome demonstrated by assessment, not a technique applied
- Re-identification not reasonably possible for anyone, including by linkage
- Judged against all means reasonably likely to be used
- Outside the scope of data protection obligations, if genuinely achieved
- A judgement that can expire as new auxiliary datasets appear
Try it first
A team replaces every email address with its SHA-256 hash and argues that a one-way function makes the dataset anonymous. What is wrong with the argument?
The hash is deterministic and the input space is enumerable. Anyone holding a list of candidate email addresses can hash the list and match, confirming presence and re-attaching the identity. Nothing has been destroyed; an identifier has been replaced with a pseudonym that is stable across datasets, which actually makes cross-dataset linkage easier. Salting per dataset helps against pre-computation but keeps the data pseudonymous rather than anonymous, and it breaks the linkage the team probably wanted the hash for. Note the same reasoning applies to embeddings, met later in this course.
The hashing point deserves emphasis because it recurs. A hash of an email address is deterministic and the domain of possible email addresses is enumerable, so anyone holding a candidate list can confirm membership by hashing it. A hash is a pseudonym with good properties, not an erasure. The same logic later applies to embeddings, which are also a one-way transform that people mistake for anonymisation.
What k-anonymity buys, and what it leaves open
An analytics team releases a dataset satisfying k-anonymity with k equal to 10 across postcode, age band and admission month. That means every combination of those three values that appears in the release is shared by at least ten records. The intuition is that you cannot single out an individual within a group of ten. That intuition is about identity, and it holds reasonably well for identity. The problem is that disclosure is not only about identity.
Suppose one equivalence class of ten records shares a single sensitive value: all ten patients have the same diagnosis. An adversary who knows their neighbour lives in that postcode, is in that age band and was admitted that month does not need to single out the individual record. Membership of the group discloses the diagnosis outright. Raising k makes the group larger and does nothing about this, because the flaw is homogeneity within the class, not the size of the class. This is the homogeneity attack, and it is the reason l-diversity, which requires a minimum spread of sensitive values within each class, and t-closeness, which requires the distribution of sensitive values within a class to resemble the overall distribution, were proposed.
Check yourself
A release satisfies l-diversity: every equivalence class contains at least three distinct diagnoses. In one class of twenty records, eighteen share the same diagnosis and the other two differ. Which objection is strongest?
Counting distinct values says nothing about how they are distributed. A class where one value dominates still lets an adversary infer that value with high confidence from group membership alone, which is the gap t-closeness addresses by requiring the within-class distribution to resemble the overall distribution. The number of quasi-identifiers and the presence of dates are not the issue here.
| Technique | What it constrains | What it does not address |
|---|---|---|
| Direct identifier removal | Obvious naming of individuals | Linkage through quasi-identifiers |
| Hashing or tokenising identifiers | Casual reading of the identifier | Confirmation by an adversary with a candidate list |
| k-anonymity | Group size for each quasi-identifier combination | Homogeneous sensitive values; adversary background knowledge |
| l-diversity | Spread of sensitive values within a class | Skewed or semantically close value distributions |
| t-closeness | Distributional similarity within a class | Utility cost; still no formal bound against arbitrary auxiliary data |
| Differential privacy | Influence of any one record on the output | Population inference; group correlation; lawfulness of collection |
The practical stance to take is that anonymisation is a risk assessment against reasonably available means, made at a point in time, and it can expire. Auxiliary datasets that did not exist when you made the assessment can appear later, and re-identification techniques improve. A release you correctly judged anonymous three years ago is not automatically anonymous today. Recording the assumptions behind the judgement, especially which external datasets you assumed an adversary could obtain, is what allows the judgement to be revisited rather than merely inherited.