K-Anonymity

A dataset satisfies k-anonymity if each combination of quasi-identifier values (attributes like ZIP code, age, or gender that can be linked to external data) appears in at least k records. This creates equivalence classes where no individual can be singled out.

• k=1: No protection—every record is unique
• k=5: Each record matches at least 4 others
• k=100: High protection, but may reduce data utility

The parameter k represents the minimum group size, directly controlling the re-identification risk.

K-anonymity distinguishes between two critical attribute types:

• Quasi-Identifiers (QIs): Attributes that do not directly identify individuals but can be combined with external datasets to re-identify records. Examples include date of birth, gender, and 5-digit ZIP code.
• Sensitive Attributes: Confidential information like medical diagnosis, salary, or voting preference that must be protected.

The model anonymizes QIs while preserving sensitive attributes for analysis, assuming the prosecutor risk model where an attacker knows a target's QI values.

Two primary techniques achieve k-anonymity:

Generalization replaces specific values with broader categories:

• Age 34 → Age range 30-39
• ZIP 94105 → ZIP prefix 9410*
• Occupation "Neurologist" → "Medical Professional"

Suppression removes or masks entire records or cell values that cannot be generalized without breaking the k threshold. This creates a trade-off between data utility and privacy protection, measured by the discernibility metric or normalized average equivalence class size.

K-anonymity has known vulnerabilities that led to stronger models like l-diversity and t-closeness:

• Homogeneity Attack: When all records in a k-anonymous equivalence class share the same sensitive value, an attacker learns the target's sensitive attribute without re-identification.
• Background Knowledge Attack: An attacker with external information can eliminate possible sensitive values within an equivalence class.

Example: If all women aged 30-39 in ZIP 9410* have the same disease, knowing a target is in that group reveals her diagnosis despite k-anonymity.

Achieving optimal k-anonymity is NP-hard, so practical implementations use heuristic algorithms:

• Datafly: Greedy algorithm that generalizes attributes with the most distinct values first
• Mondrian: Multi-dimensional partitioning that recursively splits the dataset along QI dimensions
• Incognito: Bottom-up lattice search that exploits monotonicity properties for efficiency
• Top-Down Specialization (TDS): Starts with fully generalized data and iteratively specializes attributes

Each algorithm balances computational complexity against information loss.

Quantifying the utility cost of anonymization is essential for selecting appropriate k values:

• Discernibility Penalty: Sum of squared equivalence class sizes—penalizes large, over-generalized groups
• Normalized Certainty Penalty (NCP): Measures how much each attribute value has been generalized from its original specificity
• Classification Metric: Evaluates how well anonymized data preserves patterns for machine learning tasks
• Query Error Rate: Compares aggregate query results between original and anonymized datasets

These metrics guide the privacy-utility trade-off.

An extension of k-anonymity that addresses homogeneity attacks. While k-anonymity ensures each record is indistinguishable from k-1 others, it does not guarantee diversity within the sensitive attributes of that group. L-diversity requires that each equivalence class contains at least l 'well-represented' values for sensitive attributes, preventing attackers from inferring sensitive information when all members share the same confidential value.

A refinement of l-diversity that prevents skewness attacks. T-closeness requires that the distribution of a sensitive attribute in any equivalence class is within a threshold distance t from the distribution of that attribute in the overall dataset. This prevents information leakage when an attacker knows the global distribution and can infer that a specific group deviates significantly from it.

Attributes that, individually, are not unique identifiers but can be combined to re-identify individuals when linked with external datasets. Common examples include:

• Date of birth + Gender + ZIP code
• Occupation + Employer + Age

K-anonymity operates by generalizing or suppressing these quasi-identifiers to create equivalence classes of size at least k.

The probability that an attacker can successfully link anonymized or synthetic records back to the specific real-world individual they describe. K-anonymity reduces this risk by ensuring each record blends into a crowd of size k, but does not eliminate it entirely. Modern membership inference attacks and linkage attacks using auxiliary public datasets remain viable threats that differential privacy is designed to formally bound.

The process of obscuring specific sensitive data elements by replacing them with structurally similar but inauthentic characters or values. Common techniques include:

• Character shuffling
• Substitution with realistic but fake values
• Tokenization using irreversible vaults

Data masking is often applied as a preprocessing step before k-anonymity generalization to further reduce re-identification risk in synthetic data pipelines.