K-Anonymity

K-Anonymity operates by identifying quasi-identifiers—attributes like ZIP code, age, and gender that, when combined, can uniquely identify individuals. The algorithm groups records into equivalence classes where each class contains at least k records sharing identical quasi-identifier values. This ensures an adversary cannot link a specific record to a known individual, even with access to external datasets. The core mechanism involves generalization (replacing specific values with broader categories) and suppression (removing outlier records that cannot be grouped).

To achieve indistinguishability, K-Anonymity applies domain generalization hierarchies that replace precise values with semantically meaningful broader categories. For example:

• Age 34 → Age Range 30-39
• ZIP Code 02139 → ZIP Prefix 0213*
• Salary $87,500 → Income Bracket $80K-$90K

The depth of generalization directly impacts the privacy-utility trade-off: deeper generalization provides stronger privacy but reduces data granularity for analysis. Domain experts typically define these hierarchies to preserve analytical relevance.

A critical limitation of K-Anonymity is its susceptibility to the homogeneity attack. If all k records in an equivalence class share the same sensitive attribute value (e.g., all have the same disease diagnosis), an attacker who knows a target is in that class can infer the sensitive value with certainty—even without re-identification. This occurs because K-Anonymity only protects against identity disclosure, not attribute disclosure. The attack highlights why K-Anonymity alone is insufficient for complete privacy protection.

K-Anonymity can be defeated by background knowledge attacks, where an adversary uses external information to narrow down possibilities within an equivalence class. For example, if an attacker knows a target individual is Japanese and the equivalence class contains only one Japanese person among k records, the sensitive attribute is exposed. This vulnerability arises because K-Anonymity does not account for the distribution of sensitive values within groups, motivating the development of stronger models like L-Diversity.

The minimality principle in K-Anonymity dictates that data should be generalized only as much as necessary to achieve the required k threshold. This approach preserves maximum data utility while satisfying the privacy constraint. Algorithms like Mondrian multidimensional partitioning implement this by recursively splitting data along quasi-identifier dimensions, creating equivalence classes that are as specific as possible. The principle directly addresses the privacy-utility trade-off, ensuring analysts retain the most granular data feasible under the privacy budget.

Achieving optimal K-Anonymity—finding the minimal generalization that satisfies k while maximizing utility—is NP-hard. This computational challenge has driven the development of heuristic algorithms that approximate optimal solutions efficiently:

• Datafly: Uses greedy attribute generalization
• Mondrian: Applies multidimensional recursive partitioning
• Incognito: Leverages bottom-up lattice traversal
• OLA (Optimal Lattice Anonymization): Explores generalization lattices with pruning These algorithms trade optimality for practical runtime on large-scale datasets.

An extension of k-anonymity that addresses a critical weakness: homogeneity attacks. A dataset satisfies l-diversity if, for each equivalence class defined by quasi-identifiers, there are at least l well-represented values for each sensitive attribute.

• Distinct l-diversity: Ensures at least l distinct sensitive values per group
• Entropy l-diversity: Requires the entropy of sensitive values to be at least log(l)
• Recursive (c,l)-diversity: Ensures the most frequent value does not appear too often

Without l-diversity, a k-anonymous group where all members share the same disease diagnosis still leaks sensitive information.

A privacy model that further refines l-diversity by requiring the distribution of a sensitive attribute in any equivalence class to be close to its distribution in the overall dataset. The distance between distributions must not exceed a threshold t.

• Uses Earth Mover's Distance to measure distributional divergence
• Prevents skewness attacks where l-diverse groups still reveal statistical anomalies
• Protects against similarity attacks where sensitive values are semantically close

T-closeness limits an attacker's ability to gain new knowledge about an individual beyond the global population statistics.

A set of non-sensitive attributes that, when combined, can uniquely identify an individual by linking to external datasets. Quasi-identifiers are the core target of k-anonymity transformations.

• Common examples: ZIP code, birth date, gender (87% of U.S. population uniquely identifiable by these three)
• Domain-specific: Diagnosis codes, admission dates, procedure timestamps
• Identification risk: Must be assumed that adversaries possess auxiliary information

Identifying quasi-identifiers is the critical first step before applying generalization or suppression to achieve k-anonymity.

A core k-anonymity transformation technique that replaces specific attribute values with broader, less precise categories. This creates equivalence classes of records that are indistinguishable from each other.

• Domain generalization hierarchies: ZIP code 94105 → 9410* → 941** → 94***
• Age generalization: Exact age 34 → age range 30-39 → 30-50
• Trade-off: Higher generalization levels increase privacy but reduce data utility

Generalization is preferred over suppression when some information value can be preserved through coarser granularity rather than complete removal.

A privacy transformation that completely removes or replaces certain values with a placeholder (e.g., * or NULL) to prevent re-identification. Suppression is applied when generalization would be insufficient or too distorting.

• Cell suppression: Hiding individual cell values that are outliers
• Record suppression: Removing entire rows that cannot be adequately anonymized
• Attribute suppression: Dropping entire columns that pose excessive disclosure risk

Suppression guarantees zero information leakage for the suppressed data but reduces dataset completeness. Often used in combination with generalization for optimal privacy-utility balance.

The probability that an adversary can successfully link anonymized records back to specific individuals. K-anonymity directly addresses identity disclosure, but re-identification risk encompasses broader attack vectors.

• Prosecutor risk: Likelihood that a specific known individual is in the dataset
• Journalist risk: Probability that any record can be re-identified in the population
• Marketer risk: Expected number of correct record matches across the entire dataset

Measuring re-identification risk requires modeling adversary background knowledge and available external datasets. K-anonymity provides a structural guarantee, but residual risks from attribute disclosure remain.