What is a background-knowledge attack, and why does it threaten k-anonymity even when no group is fully homogeneous?

A background-knowledge attack uses external facts the attacker already knows to eliminate candidates inside an anonymous group, narrowing the possible sensitive value — even when the group looks safely k-anonymous.

Basic k-anonymity faces two classic limitations: the homogeneity attack (all sensitive values in a group are identical) and the background-knowledge attack. The second is subtler: the attacker leverages external information — habits, associations, public facts — to eliminate candidates within an equivalence class and reveal identity or a sensitive value.

How it bites: suppose an equivalence class holds two diagnoses, "heart disease" and "viral infection," so it passes l-diversity. If the attacker knows the target is a marathon runner (very low heart-disease prior) or recently posted about being sick, that side knowledge collapses the group's apparent diversity to a near-certain guess. The group never had to be homogeneous — the attacker's own knowledge did the narrowing.

This is precisely why l-diversity alone is not enough, and why differential privacy is designed to hold even against attackers with arbitrary background knowledge.

Tip: Homogeneity is when the data leaks; background knowledge is when what the attacker already knows does the leaking. k-anonymity defends against neither.