k-Anonymity

The core mechanism involves identifying quasi-identifiers (QIDs)—attributes like ZIP code, age, and gender that are not unique on their own but can be linked to external data to re-identify individuals. k-Anonymity groups records into equivalence classes where all members share the same QID values. If an attacker knows a target's QIDs, they can only narrow the search to a group of at least k individuals, preventing exact identification.

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

• Generalization: Replacing specific values with broader categories. For example, replacing exact age '34' with an age range '30-40', or a full ZIP code '90210' with '902**'.
• Suppression: Removing or replacing values entirely with a placeholder (e.g., '*') when generalization is insufficient or creates overly distorted data. These transformations are guided by a generalization hierarchy, a structured taxonomy that defines how values can be rolled up from specific to general.

A critical weakness of k-anonymity is its failure to protect against homogeneity attacks. If all k records in an equivalence class share the same sensitive attribute value (e.g., all have the same medical diagnosis), an attacker who knows a target is in that group learns the sensitive value with certainty, even without singling them out. This limitation led to the development of stronger models like l-Diversity, which requires diversity of sensitive values within each group.

k-Anonymity does not account for an adversary's background knowledge. An attacker might know that a specific individual is not associated with a particular sensitive value. If an equivalence class contains only records with that value, the attacker can infer the target's exclusion, potentially narrowing down the remaining possibilities. This vulnerability is addressed by t-Closeness, which constrains the distribution of sensitive attributes to mirror the overall dataset distribution.

Selecting the value of k is a direct trade-off between privacy and data utility. A higher k (e.g., k=100) provides stronger privacy by creating larger, more anonymous groups but requires more aggressive generalization, which can strip the data of analytical value. A lower k (e.g., k=3) preserves more granular information but increases re-identification risk. The optimal k is context-dependent and must be evaluated against the specific threat model and the intended analytical use case.

Finding the optimal k-anonymous transformation that minimizes information loss is an NP-hard problem. In practice, heuristic and greedy algorithms are used to search the generalization hierarchy space. These algorithms iteratively generalize attributes until the minimum group size k is met, but they do not guarantee a globally optimal solution. This computational cost is a practical consideration for large, high-dimensional datasets with numerous quasi-identifiers.

A structured taxonomy used to replace specific QID values with broader, less precise categories. This is the primary operational mechanism for achieving k-Anonymity.

• Domain Generalization: A single value maps to a broader category (e.g., Age 27 → Age Range 25-30).
• Value Generalization: An entire attribute is replaced by a higher-level concept in a predefined tree (e.g., Zip Code 02138 → Zip Code 0213* → State: MA).
• The height of the hierarchy determines the maximum information loss; finding the optimal generalization level is an NP-hard problem.

The probability that an adversary can successfully link de-identified records back to specific individuals. k-Anonymity aims to reduce this risk, but it is never zero.

• Prosecutor Risk: The risk that a specific known individual is in the dataset.
• Journalist Risk: The risk that any record can be re-identified, even without a specific target.
• Marketer Risk: The risk that a large proportion of records can be linked, even if not perfectly.
• k-Anonymity primarily defends against prosecutor risk by ensuring indistinguishability within groups.