k-anonymity is a meaningful improvement over naive de-identification, but it has well-documented failure modes that every Privacy Engineer must understand.
The Homogeneity Attack
k-anonymity guarantees that an attacker cannot identify which record belongs to their target. It does not guarantee that the sensitive attribute is hidden.
Scenario: You achieve k=3. An attacker knows their neighbor Bob is "Male, Zip 9021*, Age 30–40." They find the equivalence class of 3 matching rows and look at the "Diagnosis" column:
| Zip | Gender | Age | Diagnosis |
|---|---|---|---|
| 9021* | M | 30-40 | HIV Positive |
| 9021* | M | 30-40 | HIV Positive |
| 9021* | M | 30-40 | HIV Positive |
The attacker cannot identify which row is Bob — but all three rows have the same diagnosis. They now know with certainty that Bob is HIV Positive. The sensitive attribute lacked diversity within the equivalence class. This is the Homogeneity Attack.
The Background Knowledge Attack
Even with diverse sensitive attributes, an attacker with external knowledge can narrow down the possibilities. If the attacker knows Bob is a vegetarian and the dataset contains dietary information, they can eliminate rows that contradict that fact, potentially reducing the equivalence class to a single record.
Defenses: l-diversity and t-closeness
These attacks motivated two extensions to k-anonymity:
l-diversity: Each equivalence class must contain at least l distinct values for the sensitive attribute. In the example above, l-diversity would require at least 3 different diagnoses in the group of 3 rows — preventing the homogeneity attack.
t-closeness: The distribution of the sensitive attribute within each equivalence class must be statistically close (within threshold t) to its distribution in the overall dataset. This prevents an attacker from inferring that a group has an unusually high rate of a sensitive condition.
The key insight for senior engineers: k-anonymity and its extensions are syntactic privacy models — they define structural properties of the dataset but make no formal probabilistic guarantees about what an attacker can learn. Differential Privacy (next section) is a semantic model that provides mathematical guarantees regardless of what background knowledge the attacker possesses.
A common interview question: "Why isn't k-anonymity sufficient for modern privacy requirements?" The answer has two parts: (1) the homogeneity attack shows it doesn't protect sensitive attribute values, and (2) it provides no formal guarantee against attackers with background knowledge. Differential Privacy is the answer to both problems because its guarantee holds even against computationally unbounded adversaries with arbitrary side information.