k-anonymity and its limits against linkage attacks

WHAT THIS TESTS This checks whether you know a foundational anonymization technique, can apply it concretely, and critically understand why it is necessary but not sufficient, which leads to its successors.

A GOOD ANSWER COVERS Define k-anonymity: a released dataset is k-anonymous if every record is indistinguishable from at least k minus one other records with respect to the quasi-identifiers, the attributes that are not unique alone but together can re-identify someone, such as zip code, age, and gender. To apply it to patient records, you transform the quasi-identifiers so that records fall into equivalence groups of size at least k. Use generalization, for example truncating a five-digit zip to its first three digits and bucketing exact age into ranges like thirty to forty, and use suppression to drop or mask rare outlier records that cannot be grouped. The diagnosis is the sensitive attribute you want to protect, not a quasi-identifier. Then explain the limits. The homogeneity attack: if all k records in a group share the same diagnosis, knowing someone is in that group reveals their diagnosis even though k-anonymity holds. The background-knowledge attack: an attacker who knows extra facts about the target can rule out group members and link them to a record. These gaps motivate l-diversity, which requires diverse sensitive values per group, and t-closeness, which constrains the sensitive-value distribution.

COMMON WRONG ANSWERS Treating k-anonymity as a complete privacy guarantee. Generalizing the sensitive attribute instead of the quasi-identifiers. Ignoring suppression of outliers, leaving unique records. Not naming any concrete attack that defeats it.

LIKELY FOLLOW-UPS How do l-diversity and t-closeness address these attacks? How do you choose k? How does differential privacy differ fundamentally?

ONE CONCRETE EXAMPLE You set k equal to five, generalize zips to three digits and age to ten-year bands, and suppress two unique records. A group of five patients all share zip 021, age 40 to 50. But if all five carry the diagnosis HIV, an attacker who knows their neighbor is a forty-five-year-old in that zip immediately learns the diagnosis, a homogeneity attack that k-anonymity alone cannot stop.