k-Anonymity and Re-identification

Using 1990 US census data, Latanya Sweeney estimated that 87% of the population, 216 million of 248 million people, were likely unique on just three fields: five-digit ZIP code, gender and date of birth (Sweeney, 2000, Simple Demographics Often Identify People Uniquely, Carnegie Mellon Data Privacy Working Paper 3). A later analysis of the 2000 census put the figure at 63% (Golle, 2006, Revisiting the Uniqueness of Simple Demographics in the US Population, WPES). Either number means a "de-identified" medical table that keeps those fields can be joined to a voter roll that also has names.

Fields like these are quasi-identifiers: harmless alone, identifying in combination. PII Detection and Redaction Pipelines removes direct identifiers; this concept is about what remains.

The guarantee

A release \(T\) with quasi-identifier attributes \(QI\) is k-anonymous if every record shares its quasi-identifier values with at least \(k-1\) others:

(Sweeney, 2002, k-Anonymity: A Model for Protecting Privacy, IJUFKS 10(5), 557-570). The groups of identical quasi-identifiers are equivalence classes. A linker who knows someone's quasi-identifiers can narrow them to a class of at least \(k\) records, never to one.

It is achieved by generalisation (ZIP 02138 becomes 021**, age 34 becomes 30-39) and suppression (dropping outlier rows). Finding the k-anonymisation that loses the least information is NP-hard (Meyerson & Williams, 2004, On the Complexity of Optimal k-Anonymity, PODS), so practical tools use heuristics.

What it does not stop

Consider a 3-anonymous class:

If you know your neighbour is a woman in her thirties in 021**, you learn her diagnosis without identifying her row. This homogeneity attack, and attacks using background knowledge, motivated \(\ell\)-diversity, which requires at least \(\ell\) well-represented sensitive values per class (Machanavajjhala et al., 2006, ℓ-Diversity: Privacy Beyond k-Anonymity, ICDE). Diverse values can still be skewed, so t-closeness requires each class's sensitive distribution to lie within distance \(t\) of the whole table's (Li, Li & Venkatasubramanian, 2007, t-Closeness, ICDE). Each patch answers the last attack and assumes the attacker's knowledge stops there.

High dimensions: the Netflix Prize

k-anonymity presumes you can list the quasi-identifiers. In sparse, high-dimensional data every attribute is one. Netflix released more than 100 million movie ratings with subscriber names removed. Narayanan and Shmatikov showed that knowing 8 of a subscriber's ratings, 2 of which may be wrong, with dates accurate to within 14 days, uniquely identifies 99% of records; two ratings with dates within 3 days suffice for 68%. Without any dates, 6 of 8 ratings of films outside the 500 most popular identify 84%. They matched records against public IMDb reviews (Narayanan & Shmatikov, 2008, Robust De-anonymization of Large Sparse Datasets, IEEE S&P, arXiv:cs/0610105).

Aggarwal showed the structural reason: as the number of quasi-identifying dimensions grows, k-anonymising without destroying the data becomes infeasible (Aggarwal, 2005, On k-Anonymity and the Curse of Dimensionality, VLDB). A generative-model study later estimated that 15 demographic attributes would correctly re-identify 99.98% of Americans in any dataset (Rocher, Hendrickx & de Montjoye, 2019, Nature Communications 10, 3069).

When it breaks, and what replaced it

It is a property of one table, not of a release process. Two independently k-anonymised releases about overlapping people can be intersected to shrink classes below \(k\), a composition attack (Ganta, Kasiviswanathan & Smith, 2008, Composition Attacks and Auxiliary Information in Data Privacy, KDD). Differential privacy was built for exactly this: it constrains the mechanism, holds regardless of auxiliary information, and degrades predictably under composition.

The attacker's knowledge is assumed, not bounded. Declaring which columns are quasi-identifiers is a guess about the adversary, and the Netflix attack used columns nobody labelled.

The field genuinely disagrees about practical risk. A systematic review found attacks re-identified about 26% of records across studies, but only two of fourteen targeted data de-identified to existing standards, and the one on health data re-identified 0.013% (El Emam et al., 2011, PLoS ONE 6(12): e28071). De-identification practitioners read this as evidence that standards-based, risk-assessed release works; re-identification researchers answer that each demonstrated attack used data its publishers believed safe, and that tomorrow's auxiliary data is unknown today.

Utility collapses before privacy arrives. Generalising enough to defeat linkage on rich data often removes the signal a model would have learned, which is why ML training sets are usually protected with DP-SGD or access controls rather than published k-anonymous.