k-Anonymity Fundamentals
What you'll learn: How k-anonymity protects privacy by ensuring every record blends into a crowd of at least k similar records.
The Core Idea
After removing direct identifiers and identifying quasi-identifiers (like age, zip code, gender), you still face re-identification risk. k-anonymity solves this by requiring that every record in your dataset is indistinguishable from at least k-1 other records when looking at those quasi-identifiers.
Think of it like witness protection: you don't just change someone's name—you make sure there are at least k-1 other people in the city who match their visible characteristics (age range, neighborhood, appearance). An attacker can't pick you out from the crowd.
How It Works
For a dataset to satisfy k-anonymity:
- Every unique combination of quasi-identifier values must appear at least k times
- If your dataset has k=3, then every person's (age, zip code, gender) combination must match at least 2 others
- Higher k = stronger privacy protection (but more data utility loss)
The Indistinguishability Guarantee
When k=5, an adversary with auxiliary information about someone's quasi-identifiers can narrow them down to a group of 5 records—but cannot identify which specific one is the target. This limits re-identification risk to 1/k at best.
Achieving k-Anonymity
You typically use generalization (e.g., exact age → age ranges) or suppression (removing outlier records) to create equivalence classes—groups of records sharing identical quasi-identifier values—each containing at least k members.
Key Takeaway: k-anonymity protects privacy by ensuring each record hides in a crowd of at least k indistinguishable records based on quasi-identifiers, making re-identification probabilistically bounded to 1/k.