K-Anonymity

A dataset satisfies k-anonymity if each record is indistinguishable from at least k-1 other records with respect to the quasi-identifiers (attributes like ZIP code, age, and gender that can be linked to external data). This prevents an attacker from isolating a specific individual's record even when they possess background knowledge. For example, if k=5, any combination of quasi-identifier values must appear at least 5 times in the dataset.

The k-anonymity model distinguishes between two critical data categories:

• Quasi-identifiers: Attributes that do not directly identify an individual but can be combined to re-identify records when linked with external datasets (e.g., birth date, gender, postal code)
• Sensitive attributes: The confidential information being protected (e.g., medical diagnosis, salary, transaction amount) The anonymization process focuses on generalizing or suppressing quasi-identifiers while preserving the analytical utility of sensitive attributes.

Generalization replaces specific quasi-identifier values with broader, less precise categories using predefined domain generalization hierarchies. A ZIP code like 02138 might be generalized to 0213*, then to 021**, and finally to 02***. Similarly, age 34 becomes the range 30-39, then 30-49. The height of the hierarchy determines the trade-off between privacy protection and data utility—higher generalization provides stronger anonymity but reduces analytical granularity.

When generalization cannot achieve the desired k threshold without excessive information loss, suppression removes entire records or specific cell values from the dataset. Cell suppression blanks individual quasi-identifier values that create unique combinations, while tuple suppression removes entire outlier rows. Suppression is typically applied sparingly as a last resort, since each suppressed record permanently reduces the dataset's statistical power and may introduce sampling bias.

A critical limitation of k-anonymity is its susceptibility to the homogeneity attack. If all k records in an equivalence class share the same sensitive attribute value, an attacker who knows a target is in that class can infer the sensitive information with certainty—even though they cannot identify the exact record. For instance, if all 5 individuals aged 30-39 in ZIP code 021** have the same disease, the diagnosis is exposed. This weakness led to the development of l-diversity as a stronger privacy model.

The background knowledge attack exploits an attacker's external information to narrow down sensitive attribute values within an equivalence class. Even when sensitive values are diverse, an attacker who knows a specific individual does not have a particular condition can eliminate that possibility and infer the actual value. This vulnerability motivated the creation of t-closeness, which requires the distribution of sensitive attributes in each equivalence class to mirror the overall dataset distribution, preventing probabilistic inference attacks.

A set of non-sensitive attributes that, when combined, can uniquely or near-uniquely identify an individual by linking to external datasets. Gender, date of birth, and postal code are classic quasi-identifiers—87% of the U.S. population is uniquely identifiable from just these three attributes. K-anonymity protects against this by ensuring every combination of quasi-identifier values appears at least k times in the released dataset.

A disclosure control technique that replaces specific quasi-identifier values with broader, less precise categories to achieve k-anonymity. Common strategies include:

• Attribute suppression: Removing the most identifying columns entirely
• Value generalization: Replacing exact ages with age ranges (e.g., 34 → 30-40)
• Hierarchical generalization: Rolling up postal codes to city or state level This creates equivalence classes where individuals become indistinguishable from one another.

The removal of entire records or specific cell values that would violate the k-anonymity threshold. Tuple suppression deletes outlier rows that cannot be grouped with at least k-1 other records. Cell suppression blanks individual attribute values while preserving the rest of the record. Excessive suppression reduces data utility, creating a direct trade-off between privacy protection and analytical value.

An extension of k-anonymity that addresses the homogeneity attack—where all k records in an equivalence class share the same sensitive value. L-diversity requires each k-anonymous group to contain at least l distinct values for sensitive attributes. Variants include:

• Distinct l-diversity: At least l different sensitive values per group
• Entropy l-diversity: The entropy of sensitive value distribution exceeds a threshold
• Recursive (c,l)-diversity: No single value dominates the group's distribution

A refinement of l-diversity that prevents skewness attacks by requiring the distribution of sensitive values in each equivalence class to be within a threshold distance t from the global distribution. This uses distance metrics like the Earth Mover's Distance to measure divergence. T-closeness prevents scenarios where an attacker learns that a target's sensitive value is statistically rare, even if multiple distinct values exist in the group.

A mathematically rigorous privacy framework that provides stronger guarantees than k-anonymity by adding calibrated statistical noise to query results. Unlike syntactic models like k-anonymity, differential privacy is semantic—it guarantees that an adversary cannot determine whether any specific individual's data was included in the dataset, regardless of external knowledge. The privacy budget parameter epsilon (ε) controls the trade-off between accuracy and protection.