K-Anonymity

The core mechanism of k-anonymity targets linkage attacks—the most common re-identification vector. Quasi-identifiers are attributes like ZIP code, birth date, and sex that are not themselves direct identifiers but can uniquely identify individuals when combined with external datasets. K-anonymity forces these attributes into equivalence classes of size ≥ k, ensuring an attacker joining the released data with a voter registration or hospital discharge table cannot isolate a single individual. The model assumes the sensitive attributes (e.g., diagnosis) are not known to the attacker a priori.

K-anonymity is enforced through two primary transformation operations on quasi-identifiers:

• Generalization: Replacing specific values with broader, less precise categories. A birth date of '1984-03-15' becomes '1984' or '1980-1989'. ZIP code '02138' becomes '0213*'.
• Suppression: Removing entire records or specific cell values that cannot be generalized without violating the k threshold. Outlier records that form small equivalence classes are typically suppressed entirely. The optimal balance between generalization and suppression to minimize information loss while achieving k-anonymity is an NP-hard problem, requiring heuristic algorithms like Mondrian multidimensional partitioning.

K-anonymity is vulnerable to two critical attacks that led to its successor models:

• Homogeneity Attack: If all k records in an equivalence class share the same sensitive attribute value (e.g., all have 'HIV-positive'), the sensitive information is revealed despite k-anonymity. The attacker knows the individual is in the group and therefore learns the diagnosis.
• Background Knowledge Attack: An attacker with external knowledge can eliminate possibilities. If an equivalence class contains records with diagnoses 'cancer' and 'flu', and the attacker knows the target does not have cancer, the diagnosis is uniquely revealed. These limitations motivated the development of l-diversity and t-closeness.

The parameter k represents the minimum equivalence class size and directly controls the privacy-utility trade-off:

• k=2: Minimal protection, easily broken with small external knowledge.
• k=5 to 10: Common operational range for low-sensitivity data.
• k=100+: Strong protection for high-sensitivity data, but causes heavy generalization and significant information loss. Higher k values reduce the granularity of quasi-identifiers, degrading the analytical utility of the dataset for machine learning training. The optimal k depends on the threat model, data sensitivity, and the intended analytical use case.

K-anonymity is a syntactic privacy model that operates on the output dataset's structure, while differential privacy is a semantic privacy model that provides a mathematical guarantee about the indistinguishability of any individual's participation. Key differences:

• K-anonymity protects against linkage attacks on quasi-identifiers but fails against homogeneity attacks.
• Differential privacy injects calibrated noise into query results or model gradients, guaranteeing that the output distribution is nearly identical whether or not any single record is included.
• K-anonymity produces a modified dataset for release; differential privacy typically governs the query interface or training algorithm. Modern privacy engineering often layers both approaches.

Several algorithms operationalize k-anonymity with different optimization strategies:

• Datafly: A greedy algorithm that iteratively generalizes the attribute with the most distinct values until k-anonymity is satisfied.
• Mondrian: A top-down partitioning algorithm that recursively splits the multidimensional quasi-identifier space, enforcing k-anonymity at each partition. It is widely used for its efficiency and ability to handle high-dimensional data.
• Incognito: Uses a bottom-up lattice traversal with pruning properties to find all valid k-anonymous full-domain generalizations.
• OLA (Optimal Lattice Anonymization): Finds the globally optimal generalization with minimal information loss using branch-and-bound search.

A direct extension of k-anonymity that addresses the homogeneity attack. A dataset satisfies l-diversity if each k-anonymous equivalence class contains at least l distinct values for the sensitive attribute.

• Prevents attackers from inferring sensitive values when all records in a group share the same attribute
• Example: If k=3 and all 3 people have the same disease, anonymity is broken
• Variants include entropy l-diversity and recursive (c,l)-diversity

Refines l-diversity by requiring that the distribution of sensitive attributes in each equivalence class closely mirrors the overall distribution in the dataset. The distance between distributions must not exceed a threshold t.

• Defends against skewness attacks where l-diversity alone fails
• Uses Earth Mover's Distance to measure distributional divergence
• Prevents semantic leakage when sensitive values are semantically similar
• More computationally intensive than k-anonymity or l-diversity

A set of non-sensitive attributes that, when combined, can uniquely or near-uniquely identify an individual when linked with external datasets. Identifying and controlling quasi-identifiers is the foundational step in applying k-anonymity.

• Classic example: {ZIP code, gender, date of birth} uniquely identifies 87% of US residents
• Must be generalized or suppressed during anonymization
• Selection is context-dependent and requires threat modeling
• Overlooked quasi-identifiers are the primary cause of re-identification

The process of linking anonymized records back to specific individuals by correlating quasi-identifiers with auxiliary datasets. This is the primary attack vector that k-anonymity is designed to prevent.

• Linkage attack: Matching anonymized data with public voter rolls
• Prosecutor re-identification: Verifying a known individual is in the dataset
• Journalist re-identification: Finding any identifiable individual
• Famous case: Netflix Prize dataset re-identified using IMDb reviews

The processing of personal data to replace direct identifiers with artificial pseudonyms, rendering the data unlinkable to a specific individual without separately stored additional information. Unlike k-anonymity, pseudonymized data is still considered personal data under GDPR.

• Differs from anonymization: reversible with the key
• Often used as a defense-in-depth layer alongside k-anonymity
• Enables data utility while reducing direct identifiability
• Requires strict separation of pseudonym mapping tables