K-Anonymity

The core mechanism of k-anonymity involves identifying and transforming quasi-identifiers—attributes like ZIP code, birth date, and gender that, when combined, can uniquely identify individuals. Generalization replaces specific values with broader ranges (e.g., birth year instead of full date), while suppression removes entire attribute values. The goal is to create equivalence classes where each group contains at least k records sharing identical quasi-identifier values.

The parameter k represents the minimum size of each equivalence class. A higher k value provides stronger privacy but degrades data utility. Common implementations include:

• k=2: Minimal protection, easily broken by background knowledge attacks
• k=5: Baseline for many healthcare datasets under HIPAA Safe Harbor
• k=11: Recommended threshold for high-sensitivity census data
• k=100+: Used in differential privacy systems for provable guarantees

A critical limitation of k-anonymity is susceptibility to the homogeneity attack. If all k records in an equivalence class share the same sensitive attribute value—such as a specific medical diagnosis—an attacker who knows a target belongs to that class immediately learns the sensitive information. This occurs because k-anonymity does not enforce diversity within the sensitive attributes, only indistinguishability on quasi-identifiers.

K-anonymity cannot defend against attackers with external knowledge about the target. If an adversary knows a specific individual is not represented by certain sensitive values in an equivalence class, they can infer the remaining possibilities. This limitation motivated the development of stronger models like l-diversity, which requires at least l distinct sensitive values per equivalence class, and t-closeness, which constrains the distribution of sensitive attributes.

Implementing k-anonymity requires defining domain generalization hierarchies—tree structures that map specific values to progressively broader categories. For example:

• ZIP Code: 94117 → 9411* → 941** → 94*** → 9****
• Age: 34 → [30-39] → [30-49] → [18-64] → * The algorithm traverses these hierarchies to find the minimal generalization level that satisfies the k threshold, balancing privacy with analytical precision.

Finding the minimal generalization that achieves k-anonymity while maximizing data utility is computationally intractable (NP-hard). Practical implementations use heuristic algorithms such as Mondrian multidimensional partitioning, Datafly, and Incognito. These greedy approaches iteratively generalize attributes with the highest cardinality until all equivalence classes meet the k threshold, trading optimality for computational feasibility on large datasets.

An extension of k-anonymity that addresses the homogeneity attack by requiring each equivalence class to contain at least l distinct values for sensitive attributes.

• Prevents attackers from inferring sensitive data when all records in a group share the same confidential value
• Distinct l-diversity is the simplest form, ensuring l different sensitive values per group
• Can be strengthened with entropy l-diversity or recursive (c,l)-diversity

A privacy model that refines l-diversity 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.

• Defends against skewness attacks where l-diversity alone is insufficient
• Uses Earth Mover's Distance to measure the divergence between distributions
• Prevents semantic leakage when sensitive values are semantically similar

A set of non-sensitive attributes that, when combined, can uniquely identify an individual by linking to external datasets.

• Classic example: {Zip Code, Gender, Date of Birth} uniquely identified 87% of the U.S. population in Sweeney's landmark study
• K-anonymity works by generalizing or suppressing quasi-identifiers
• Identifying quasi-identifiers is the critical first step in any anonymization pipeline

A decentralized machine learning technique where a model is trained across multiple edge devices or servers holding local data samples without exchanging the raw data.

• Complements k-anonymity by keeping raw data at its origin
• Only model updates (gradients) are shared with a central server
• Vulnerable to gradient leakage attacks that can reconstruct training data, requiring additional privacy measures

A cryptographic scheme that allows computation directly on encrypted data, producing an encrypted result that, when decrypted, matches the output of operations performed on the plaintext.

• Partially homomorphic schemes support only addition or multiplication
• Fully homomorphic encryption (FHE) supports arbitrary computation but remains computationally intensive
• Enables privacy-preserving queries on k-anonymized datasets without exposing the underlying records