What is k-anonymity, and what are its critical limitations?

K-anonymity ensures each record is indistinguishable from at least k−1 others, so no individual can be uniquely picked out of a group of k — but it's vulnerable to background-knowledge and homogeneity attacks.

* A 2-anonymous table: each record matches at least one other. — HTriedman (WMF), CC BY-SA 4.0, via Wikimedia Commons. *

You achieve it by generalizing/suppressing quasi-identifiers (age, ZIP, gender) until every combination is shared by at least k people. It underpins real compliance approaches like HIPAA Safe Harbor (healthcare) and FERPA (education records).

The two classic weaknesses:

• Homogeneity attack: if all k records in a group share the same sensitive value (e.g. all have the same diagnosis), you learn that value even without isolating the individual. (This is what l-diversity tries to fix.)
• Background-knowledge attack: an adversary uses external information to eliminate possibilities and narrow the group back down to one person.

Tip: k-anonymity hides who you are in a crowd, but not necessarily what is true about the crowd — that gap is its Achilles' heel.

Go deeper:

• k-anonymity (Wikipedia) — quasi-identifier generalization plus the homogeneity and background-knowledge attacks.