What is a background knowledge attack against a k-anonymous dataset?

An attacker uses outside knowledge to eliminate possibilities within an equivalence class, narrowing down the sensitive value.

Even with diverse sensitive values in a class, an attacker who knows the victim is in that class can apply external facts to prune the candidates. Example: knowing "Jan doesn't have heart disease" lets the attacker strike the "Cardiac" record from Jan's equivalence class — and if only a couple of values remain, the probable diagnosis is revealed.

This shows that anonymity guarantees are relative to an attacker model: they hold only against the knowledge you assumed. Real-world adversaries bring side information you didn't account for.

Tip: Every anonymity claim has an implicit "...assuming the attacker knows only X." Document that assumption, or the guarantee is meaningless.

Go deeper:

• l-diversity (Wikipedia) — describes the background-knowledge attack on k-anonymity.