K-Anonymity

The fundamental rule: each released record must be identical to at least k-1 other records with respect to quasi-identifiers (attributes like ZIP code, age, or gender that can be linked to external data). This creates an equivalence class of size k, ensuring an attacker cannot uniquely identify an individual even if they know the quasi-identifiers. For example, if k=5, any combination of quasi-identifiers must appear at least 5 times in the dataset.

Quasi-identifiers are attributes that are not direct identifiers (like name or SSN) but can be combined to re-identify individuals when linked with external datasets. Common examples include:

• Demographics: Date of birth, gender, ZIP code
• Location data: GPS coordinates, census tract
• Temporal markers: Admission date, discharge date Identifying all quasi-identifiers is the critical first step before applying suppression or generalization techniques.

Generalization replaces specific values with broader, less precise categories to achieve k-anonymity. Common strategies include:

• Domain generalization: Replacing exact ZIP codes with city or state-level regions
• Hierarchical generalization: Using taxonomy trees (e.g., age 34 → age range 30-40)
• Suppression: Removing outlier records or cell values that prevent achieving k This creates a deliberate information loss that must be balanced against analytical utility.

A critical weakness of k-anonymity: if all k records in an equivalence class share the same sensitive attribute value, an attacker learns that value without re-identifying the exact individual. For example, if all 5 people in a k=5 group have the same medical diagnosis, knowing someone is in that group reveals their condition. This led to the development of l-diversity, which requires diversity of sensitive values within each equivalence class.

Another limitation where an attacker uses external knowledge to narrow down possibilities within an equivalence class. Even with diverse sensitive values, if an attacker knows a target individual does not have certain attributes, they can eliminate possibilities. This vulnerability motivated t-closeness, which requires the distribution of sensitive values in each equivalence class to be close to the overall distribution in the dataset, preventing probabilistic inference.

Two primary operations achieve k-anonymity:

• Cell suppression: Replacing specific values with NULL or asterisks, preserving other data at full precision but creating gaps
• Attribute generalization: Broadening values across entire columns, maintaining completeness but reducing granularity Tuple suppression (removing entire outlier rows) is used as a last resort when generalization would cause excessive information loss. The optimal strategy depends on the downstream analytical use case.

An extension of K-Anonymity that addresses the homogeneity attack vulnerability. While K-Anonymity ensures each record is indistinguishable from k-1 others, L-Diversity requires that each equivalence class contains at least L well-represented values for sensitive attributes. This prevents attackers from inferring sensitive information when all records in a k-anonymous group share the same sensitive value, such as a disease diagnosis.

A refinement of L-Diversity that prevents skewness attacks and similarity attacks. T-Closeness mandates that the distribution of a sensitive attribute in any equivalence class must be within a threshold distance t from the distribution of the attribute in the overall dataset. This uses distance measures like the Earth Mover's Distance to ensure the semantic closeness of sensitive values does not leak information.

Attributes that are not unique identifiers by themselves but can be combined to re-identify individuals when linked with external datasets. Common examples include the triplet of {Date of Birth, Gender, ZIP Code}, which uniquely identifies 87% of the U.S. population. K-Anonymity operates by generalizing or suppressing these quasi-identifiers to create equivalence classes of size k or greater.

The statistical probability that an attacker can link anonymized records back to specific individuals by cross-referencing quasi-identifiers with external datasets. K-Anonymity directly mitigates this by ensuring a 1/k probability of correct re-identification within any equivalence class. However, this protection degrades if the same individual appears in multiple anonymized releases, enabling intersection attacks.

The primary technique used to achieve K-Anonymity by replacing specific attribute values with broader, less precise categories. This includes domain generalization hierarchies where, for example, a specific age of 34 is replaced with an age range of [30-40], or a full ZIP code 02138 is truncated to 0213*. The depth of generalization directly impacts the privacy-utility trade-off.