K-Anonymity

The core principle states that for any given combination of quasi-identifiers (attributes like ZIP code, age, or gender that can be linked to external data), there must be at least k records sharing that exact combination. This creates an equivalence class where an attacker cannot isolate a single individual. For example, if k=5, any query filtering by quasi-identifiers will return at least 5 rows, making it impossible to pinpoint one person's sensitive attributes like medical conditions or salary.

To achieve k-anonymity, data is transformed through two primary operations:

• Generalization: Replacing specific values with broader categories. A birth date of '1985-07-14' becomes a birth year of '1985' or an age range of '30-40'.
• Suppression: Removing or masking entire attribute values or records when generalization is insufficient. This creates a generalization hierarchy (e.g., City → County → State → Country) where higher levels provide stronger privacy at the cost of reduced data utility for analysis.

A critical weakness of k-anonymity is the homogeneity attack. If all k records in an equivalence class share the same sensitive attribute value, the attacker learns that value without needing to identify the exact individual. For instance, if all 5 people aged 30-40 in ZIP code 10001 have 'HIV-Positive' as their medical condition, the privacy is broken despite k=5. This limitation led to the development of stronger models like l-diversity.

K-anonymity does not protect against adversaries with external knowledge about the distribution of sensitive attributes. In a background knowledge attack, an attacker uses known statistical correlations to infer sensitive values. For example, knowing that a specific demographic group has a very low incidence of a particular disease allows the attacker to eliminate that possibility for a target individual, even within a k-anonymous group, effectively reducing the anonymity set.

The effectiveness of k-anonymity depends entirely on correctly identifying the quasi-identifier (QI) set—attributes that can be linked to external datasets like voter rolls or public records. Common QIs include:

• Demographics: Date of birth, gender, ZIP code
• Physical traits: Height, weight
• Transaction patterns: Purchase history timestamps Misclassifying a QI as a non-identifying attribute leaves the dataset vulnerable to re-identification attacks through linkage with auxiliary data sources.

Finding the minimal generalization and suppression to achieve k-anonymity is an NP-hard computational problem. Practical algorithms use greedy heuristics or genetic algorithms to approximate the optimal solution. The Mondrian multidimensional algorithm is a widely-used approach that recursively partitions the data space along QI dimensions, creating axis-parallel regions that satisfy the k constraint while minimizing information loss measured by metrics like the Discernibility Penalty or Normalized Certainty Penalty (NCP).

An extension of k-anonymity that addresses the homogeneity attack by requiring each equivalence class to contain at least l 'well-represented' values for sensitive attributes. If a k-anonymous group all shares the same sensitive value—such as a specific disease—an attacker can infer that attribute without re-identifying the individual. L-diversity ensures diversity within each group, though it remains vulnerable to skewness and similarity attacks where sensitive values are semantically close or unevenly distributed.

A refinement of l-diversity that prevents attribute disclosure by requiring the distribution of a sensitive attribute in any equivalence class to be within a threshold t of its distribution in the overall dataset. Measured using the Earth Mover's Distance, t-closeness limits an attacker's ability to gain new information about an individual beyond what the global distribution already reveals. This addresses l-diversity's failure against skewness attacks where an attacker learns that a target has a rare attribute value simply because it appears disproportionately in their group.

A mathematical framework providing provable privacy guarantees that k-anonymity cannot offer. Rather than syntactic anonymization, differential privacy adds calibrated noise—typically from a Laplace or Gaussian distribution—to query results or model parameters. The key parameter epsilon (ε) quantifies the privacy loss budget: lower values mean stronger privacy. Unlike k-anonymity, differential privacy is robust against auxiliary information attacks because its guarantee holds regardless of what external data an adversary possesses. It is the gold standard for privacy-preserving machine learning and census data release.

Attributes that, individually, do not uniquely identify an individual but can do so when combined with other quasi-identifiers or linked to external datasets. Common examples include:

• Date of birth
• ZIP or postal code
• Gender
• Occupation

K-anonymity operates by generalizing or suppressing quasi-identifiers so that each combination appears at least k times. The prosecutor re-identification risk model explicitly measures the probability of linking a quasi-identifier group to a specific individual, making accurate quasi-identifier selection the most critical step in any k-anonymization process.

A de-anonymization technique that links supposedly anonymized records back to specific individuals by correlating quasi-identifiers with auxiliary external data sources. The landmark example is the Netflix Prize dataset, where researchers re-identified users by linking anonymized movie ratings with public IMDb reviews. K-anonymity directly defends against this by ensuring each quasi-identifier combination maps to at least k individuals, making it impossible to pinpoint a single person even with perfect auxiliary information. However, k-anonymity does not protect against attribute disclosure within the group.

The primary technique used to achieve k-anonymity by replacing specific attribute values with broader, less precise categories. Common generalization hierarchies include:

• Numerical: Replacing exact age (34) with an interval (30-39)
• Categorical: Rolling up ZIP codes (94105) to city (San Francisco) or state (California)
• Suppression: Replacing values entirely with a placeholder when generalization is insufficient

The goal is to find the minimal generalization that satisfies the k-anonymity requirement while preserving maximum data utility. Over-generalization destroys analytical value, creating a direct privacy-utility trade-off.