K-Anonymity

The core mechanism of k-anonymity focuses on quasi-identifiers—attributes like zip code, birth date, and gender that are not unique on their own but can be linked with external datasets to re-identify individuals. The model requires that every combination of quasi-identifier values appears at least k times in the released dataset.

• Example: If an attacker knows a target lives in ZIP 10001 and is 35, a 2-anonymous dataset ensures at least one other record shares those exact attributes.
• Key distinction: Direct identifiers (name, SSN) are removed; quasi-identifiers are generalized or suppressed.

An equivalence class is the set of all records in a k-anonymized dataset that share identical quasi-identifier values. The size of each equivalence class must be ≥ k to satisfy the privacy guarantee.

• Homogeneity risk: If all records in an equivalence class share the same sensitive attribute value (e.g., a specific disease), attribute disclosure occurs even though identity is protected.
• Mitigation: l-diversity extends k-anonymity by requiring diversity of sensitive values within each equivalence class.

Generalization replaces specific quasi-identifier values with broader, less precise categories to create larger equivalence classes. This is structured through domain generalization hierarchies.

• Numerical example: Age 37 → Age range 35-40 → Age range 30-39 → Age range 20-59.
• Categorical example: Specific disease → Disease category → Suppressed.
• Trade-off: Higher generalization levels increase privacy (larger k) but reduce data utility for analysis. The goal is finding the minimal generalization that achieves the target k.

Suppression removes entire records or specific attribute values that cannot be adequately generalized to meet the k threshold without excessive distortion. This is a last-resort mechanism for outlier records.

• Cell suppression: Replacing a single quasi-identifier value with a placeholder (e.g., *) when that value is too rare.
• Tuple suppression: Removing an entire row when its quasi-identifier combination is so unique that even generalization fails to create a group of size k.
• Impact: Suppression reduces dataset size and can introduce bias if outliers are systematically removed.

While k-anonymity prevents identity disclosure, it is vulnerable to two critical attack vectors that motivated stronger models like l-diversity and t-closeness.

• Homogeneity attack: When all records in an equivalence class share the same sensitive value, the attacker learns the sensitive attribute without re-identifying the individual.
• Background knowledge attack: An attacker with external information can narrow down possibilities within an equivalence class. For example, knowing a target is Japanese when the class contains only one Japanese individual.
• Unsorted matching attack: If the order of records in the anonymized dataset matches a known external dataset, re-identification becomes trivial.

Achieving optimal k-anonymity with minimal information loss is NP-hard, so practical implementations use heuristic algorithms.

• Mondrian: A top-down greedy algorithm that recursively partitions the data space along quasi-identifier dimensions, stopping when partitions reach size k. It is widely used for its efficiency and multidimensional handling.
• Datafly: A heuristic that iteratively generalizes the attribute with the most distinct values until k-anonymity is satisfied.
• Incognito: Uses a bottom-up lattice traversal with pruning properties to find all valid k-anonymous full-domain generalizations efficiently.

The core vulnerability that K-Anonymity addresses. Quasi-identifiers are attributes like ZIP code, birth date, and gender that, when combined, can uniquely identify individuals in a dataset. An attacker links these non-sensitive attributes across multiple databases to re-identify records. K-Anonymity prevents this by ensuring every combination of quasi-identifiers maps to at least k indistinguishable records.

A direct enhancement of K-Anonymity that addresses the homogeneity attack. A dataset can satisfy K-Anonymity but still leak data if all k records share the same sensitive value (e.g., a specific disease). L-Diversity requires that each equivalence class contains at least l 'well-represented' distinct values for the sensitive attribute, preventing deterministic inference of private information.

A refinement of L-Diversity that prevents skewness attacks. If the distribution of a sensitive attribute within an equivalence class differs significantly from its global distribution, an attacker gains information. T-Closeness mandates that the distance between the intra-class and global distribution of sensitive values must not exceed a threshold t, using metrics like Earth Mover's Distance.

A mathematical framework providing a provable guarantee that the output of a computation is statistically indistinguishable whether or not any single individual is included in the input. Unlike K-Anonymity's syntactic approach, Differential Privacy uses calibrated noise (parameterized by epsilon) to mask the contribution of any single record. It is the gold standard for interactive query systems and model training via DP-SGD.

The primary operational techniques used to achieve K-Anonymity. Generalization replaces specific values with broader categories (e.g., replacing exact age '34' with an age range '30-40'). Suppression (or cell suppression) removes outlier records or values entirely that cannot be grouped into a sufficiently large equivalence class without destroying data utility. These are applied at the attribute or record level.

The adversarial technique that K-Anonymity and related privacy frameworks aim to prevent in machine learning contexts. An attacker exploits access to a model's confidence scores or prediction API to reconstruct representative features of a target class or specific training records. Defenses like confidence score masking and prediction vector truncation limit the information available to such attacks.