What is k-anonymity, and how does it protect against re-identification?
k-anonymity means that every record in a dataset is indistinguishable from at least (k-1) other records based on quasi-identifiers, making it impossible to single out any individual with certainty.
* A worked 2-anonymity example. — HTriedman (WMF), CC BY-SA 4.0, via Wikimedia Commons. *
How k-anonymity works:
A dataset is k-anonymous if every combination of quasi-identifier values appears in at least k records. For example, in a 3-anonymous dataset, every person shares their quasi-identifier combination with at least 2 other people.
Example (3-anonymity):
| ZIP Code | Age Range | Gender | Disease |
|---|---|---|---|
| 601* | 20-30 | M | Flu |
| 601* | 20-30 | M | Diabetes |
| 601* | 20-30 | M | Asthma |
Even if an attacker knows someone is male, aged 20-30, in ZIP 601*, they can't determine which of the three records belongs to their target.
Techniques to achieve k-anonymity:
- Generalization — Replace specific values with broader ranges (age 29 → age range 20-30, ZIP 60126 → 601*)
- Suppression — Remove certain values entirely
Tool: The ARX Data Anonymization Tool — an open-source tool for applying k-anonymity and other anonymization techniques to datasets.
Limitation: k-anonymity doesn't protect against attribute disclosure — if all k records share the same sensitive value (e.g., all three have "Cancer"), the attacker still learns the sensitive information.
Go deeper:
k-anonymity (Wikipedia) — the Samarati & Sweeney model, generalization and suppression.
ARX Data Anonymization Tool — the open-source tool for applying k-anonymity in practice.