The "Quasi-Identifier" Problem
Imagine a hospital releases a patient dataset. They remove the "Name" column — problem solved, right? Not quite. The dataset still contains "Zip Code," "Gender," and "Date of Birth." These are called Quasi-Identifiers (QIs): attributes that are not directly identifying on their own, but become identifying when combined.
In 1997, researcher Latanya Sweeney demonstrated that 87% of the US population can be uniquely identified using only those three attributes — Zip Code, Gender, and Date of Birth — by cross-referencing with publicly available voter registration records. Removing the name column provided almost no real protection.
The k-anonymity Property
k-anonymity is a formal property of a dataset. A dataset satisfies k-anonymity if every record is indistinguishable from at least k−1 other records with respect to the quasi-identifiers.
If k=3, and an attacker searches for "Male, born 1990, Zip 90210," they must find at least 3 rows that match exactly. They cannot determine which specific row belongs to their target. The individual hides in a crowd of at least k people.
Two techniques achieve k-anonymity:
Generalization: Replace a precise value with a broader range.
- Age: 24 → Age: 20–30
- Zip: 90210 → Zip: 902**
- DOB: 1990-03-15 → DOB: 1990
Suppression: Delete records (or attribute values) that are so unique they cannot be generalized without destroying utility. An outlier — the only 95-year-old in a dataset of 30-year-olds — may simply be removed.
Original dataset (k=1, no protection):
| Name | Zip | Gender | Age | Diagnosis |
|-------|-------|--------|-----|---------------|
| Alice | 90210 | F | 24 | Diabetes |
| Bob | 90210 | M | 31 | HIV Positive |
| Carol | 90211 | F | 27 | Flu |
After generalization to achieve k=2:
| Zip | Gender | Age | Diagnosis |
|-------|--------|-------|---------------|
| 9021* | F | 20-30 | Diabetes |
| 9021* | M | 30-40 | HIV Positive |
| 9021* | F | 20-30 | Flu |
In the generalized table, the two female records in Zip 9021* with Age 20–30 are indistinguishable — k=2 for that group.