K-anonymity and its successors

Why does removing names not remove identity, and how does k-anonymity fail?

The syntactic generation: k-anonymity, ℓ-diversity, t-closeness

We start from the failed premise, because the failure teaches a lot and these mechanisms are still everywhere. "Syntactic" means: the definition looks only at the shape of the table, not at what an adversary can do.

Why removing names does not remove identity

Remove the direct identifiers (name, national_id) and you have not removed identity. The remaining attributes (postcode, birth date, sex, job title, timestamps of activity) are quasi-identifiers: each one alone does not identify anyone, but together they form a fingerprint.

The reason is combinatorial. Suppose a dataset has d attributes and each attribute has c possible values (its cardinality). The number of possible distinct records is about c^d. Once c^d is much larger than the population N, almost every record is unique.

RelationshipWhy removing names does not remove identity →

29, 200 \times 10, 000 \times 2 \approx 584 million

$c_{i}$: possible values of attribute i
$N$: people in the dataset

Data table

Share of people alone in their combination (584 million combinations), by population
Population N	Unique on these attributes
100K	100%
115K	100%
133K	100%
154K	100%
178K	100%
205K	100%
237K	100%
274K	100%
316K	99.9%
365K	99.9%
422K	99.9%
487K	99.9%
562K	99.9%
649K	99.9%
750K	99.9%
866K	99.9%
1M	99.8%
1.15M	99.8%
1.33M	99.8%
1.54M	99.7%
1.78M	99.7%
2.05M	99.6%
2.37M	99.6%
2.74M	99.5%
3.16M	99.5%
3.65M	99.4%
4.22M	99.3%
4.87M	99.2%
5.62M	99%
6.49M	98.9%
7.5M	98.7%
8.66M	98.5%
10M	98.3%
11.5M	98%
13.3M	97.7%
15.4M	97.4%
17.8M	97%
20.5M	96.5%
23.7M	96%
27.4M	95.4%
31.6M	94.7%
36.5M	93.9%
42.2M	93%
48.7M	92%
56.2M	90.8%
64.9M	89.5%
75M	87.9%
86.6M	86.2%
100M	84.3%
115M	82.1%
133M	79.6%
154M	76.8%
178M	73.7%
205M	70.4%
237M	66.6%
274M	62.6%
316M	58.2%
365M	53.5%
422M	48.6%
487M	43.4%
562M	38.2%
649M	32.9%
750M	27.7%
866M	22.7%
1B	18%
1.15B	13.8%
1.33B	10.2%
1.54B	7.16%
1.78B	4.76%
2.05B	2.97%
2.37B	1.72%
2.74B	0.92%
3.16B	0.445%
3.65B	0.192%
4.22B	0.073%
4.87B	0.024%
5.62B	0.007%
6.49B	0.001%
7.5B	0%
8.66B	0%
10B	0%

Principle: Independence is assumed →

k-anonymity

k-anonymity forces every combination of quasi-identifiers to appear at least k times. It does this by generalization (replace a birth date by the birth year, a postcode by its first three characters) and suppression (delete rows that still stand alone). The group of rows that share the same quasi-identifiers is an equivalence class. The goal is an equivalence class of size at least k, so that a linkage attack (joining the release to an outside dataset to find a person) returns k candidates, not one.

Here is a tiny 3-anonymous release:

Postcode prefix	Birth year	Diagnosis
560	1980–1989	Diabetes
560	1980–1989	Diabetes
560	1980–1989	Diabetes
561	1970–1979	Asthma
561	1970–1979	Hypertension
561	1970–1979	Diabetes

Each class has 3 rows, so the table is 3-anonymous. Now look at the first class.

Four ways k-anonymity fails

Each failure is worth separating.

1. Homogeneity. If all k records in a class have the same sensitive value, the class size does not matter. In the table above, an attacker who knows a neighbour is in the 560 / 1980s group learns "diabetes" without identifying which row is the neighbour. ℓ-diversity patches this by requiring at least ℓ distinct sensitive values in each class.

2. Skew and semantic closeness. Distinct values are not equally informative. A class whose values are "stomach cancer", "gastric ulcer" and "gastritis" is diverse but tells the attacker "stomach problem". A class where 99% of rows share one value is diverse but still highly informative compared with the global population. t-closeness patches this by requiring each class's distribution of sensitive values to be close to the global distribution.

Notice the shape of this story. Each mechanism is defined by the attack that broke the previous one. There is no argument that t-closeness is the last patch, because the definition never talked about adversaries. It talked about the table. A syntactic privacy definition cannot terminate: for any property of the output, there is an adversary whose background knowledge makes that property insufficient.

3. Composition. This is the most damaging failure and the least discussed. Take two releases of the same population, each k-anonymous but with different generalizations. Intersect them, and the classes become much smaller than k. Example: release A groups people by (postcode prefix, birth decade); release B groups them by (full postcode, birth year range of 5 years). A person who is in a group of 3 in A and a group of 3 in B may be the only person in the intersection. k-anonymity is a property of one table, and properties of tables do not compose across tables. A data platform publishes many overlapping extracts, so composition failure is the normal case, not an unusual one. This is exactly what happened to Dr. Adaeze's second extract.

4. Dimensionality. In high-dimensional or sparse data (purchases, locations, ratings, clickstreams, anything a data platform really holds), reaching k-anonymity means generalizing until almost all information is gone. The well-known re-identifications of sparse behaviour datasets are not clever attacks. They are the direct consequence of c^d being far larger than N, which makes suppression the only reachable solution. k-anonymity works on a handful of low-cardinality demographic columns. It does not work on the kind of data that data engineering produces.

On top of this, finding the optimal generalization is NP-hard (no known efficient algorithm), so real tools use heuristics, and the utility loss is larger than the theoretical minimum.