K-Anonymity

The k value defines the minimum size of an equivalence class—a group of records sharing identical quasi-identifier values. A higher k provides stronger privacy but degrades data utility. For example, with k=5, an attacker cannot distinguish a target individual from at least 4 others in any released dataset.

• k=2: Minimal protection, vulnerable to linkage attacks
• k=5: Common baseline for healthcare datasets
• k=100+: High privacy, significant information loss

Quasi-identifiers (QIDs) are attributes that do not uniquely identify an individual alone but can do so when combined—such as date of birth, zip code, and gender. The critical challenge is correctly identifying which columns constitute QIDs before applying anonymization.

• Latanya Sweeney demonstrated that 87% of the U.S. population is uniquely identifiable using only {zip code, gender, date of birth}
• QID selection requires domain expertise and threat modeling
• Overlooking a QID can completely undermine the k-anonymity guarantee

Generalization replaces specific values with broader categories to create equivalence classes. A generalization hierarchy defines the levels of abstraction—for example, a zip code 02139 can be generalized to 0213*, then 021**, then 02***.

• Domain generalization: Applying the same transformation to all records
• Value generalization: Applying different levels to different records
• The goal is to find the minimal generalization that satisfies the k requirement while preserving analytical utility

Suppression removes entire records or specific attribute values that cannot be adequately generalized without breaking the k threshold. Outlier records with rare combinations of quasi-identifiers are typically suppressed.

• Cell suppression: Hiding individual cell values
• Tuple suppression: Removing entire outlier records
• Excessive suppression reduces dataset representativeness and can introduce selection bias in downstream analyses

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 re-identification. For example, if all 5 patients in a group have HIV=positive, privacy is breached.

• This vulnerability motivated the development of l-diversity
• Requires diversity of sensitive values within each equivalence class
• Particularly dangerous in small datasets with limited variability

The background knowledge attack exploits an attacker's external information about the sensitive attribute's distribution. Even with diverse values in an equivalence class, knowing that a target individual is unlikely to have certain values can enable probabilistic inference.

• Example: Knowing a patient is male eliminates pregnancy-related conditions
• This led to the t-closeness extension of k-anonymity
• Requires the distribution of sensitive values in each equivalence class to mirror the overall population distribution

An extension of K-Anonymity that addresses the homogeneity attack by requiring each equivalence class to contain at least l 'well-represented' sensitive values. While K-Anonymity ensures indistinguishability, it fails if all k records share the same sensitive attribute (e.g., a disease). L-Diversity mandates diversity within the group, though distinct L-Diversity (ensuring l different values) is a common instantiation. It remains vulnerable to skewness attacks if the distribution of sensitive values is unbalanced.

A refinement of L-Diversity that mitigates skewness and similarity attacks. T-Closeness requires the distribution of a sensitive attribute in any equivalence class to be within a threshold t of the distribution of the attribute in the overall dataset. It uses Earth Mover's Distance to measure the difference between distributions, preventing an attacker from gaining information simply by knowing the global distribution differs from the group's distribution.

A set of non-sensitive attributes that, when combined, can uniquely or nearly uniquely identify an individual by linking to external datasets. K-Anonymity operates directly on quasi-identifiers.

• Examples: {Date of Birth, Gender, Zip Code} is a classic quasi-identifier.
• Mechanism: Generalization (replacing a specific zip code with a region) and suppression (removing a value) are applied to quasi-identifiers to achieve K-Anonymity.
• Challenge: Identifying which attributes constitute a quasi-identifier is a complex, context-dependent task.

A formal, mathematical privacy framework that provides a provable guarantee against membership inference attacks. Unlike K-Anonymity, which is a syntactic property of a dataset, differential privacy is a property of an algorithm. It ensures that the output of a computation is statistically indistinguishable whether or not any single individual's record is included, typically by injecting calibrated noise (e.g., Laplace or Gaussian). It is the gold standard for interactive query systems.

An adversarial technique where an attacker determines whether a specific individual's data record was part of a model's training dataset. K-Anonymity is directly vulnerable to this if an attacker knows a target's quasi-identifier values and finds them in a released dataset. The attack exploits differences in model behavior on seen versus unseen data. Differential privacy is the primary defense, as it mathematically bounds the attacker's ability to infer membership.

The core operational technique for achieving K-Anonymity. It involves replacing specific attribute values with broader, less precise categories to create equivalence classes of size at least k.

• Domain Generalization Hierarchy: A tree structure defining valid generalizations (e.g., City → County → State → Country).
• Full-domain vs. Cell: Full-domain generalization applies the same level of abstraction to all values in an attribute, while cell generalization allows different levels for different tuples.
• Trade-off: Higher generalization increases privacy but reduces data utility.