Data Anonymization

Data anonymization transforms datasets containing Personal Identifiable Information (PII) so that individuals cannot be readily identified, while preserving statistical utility for analysis.

Key Attribute Classifications

Attribute Type	Description	Examples
Direct Identifiers	Uniquely identifies an individual directly.	Full Name, SSN, Passport Number, Email
Quasi-Identifiers (QIs)	Attributes that do not identify on their own, but can uniquely identify when combined or linked with external datasets.	ZIP Code, Birth Date, Gender, Job Title
Sensitive Attributes	Private attributes associated with individuals that require protection from disclosure.	Medical Diagnosis, Salary, Credit Score

Core Anonymization Techniques

1. Suppression / Masking: Removing or masking sensitive attributes or identifiers entirely (e.g., masking credit card digits **** **** **** 1234).
2. Generalization / Bucketing: Replacing specific values with broader categories or intervals (e.g., replacing exact age 29 with range 20–29, or ZIP code 94043 with 940**).
3. Perturbation / Noise Addition: Adding random noise (e.g., Laplace or Gaussian noise) to numerical attributes to obscure exact values while preserving aggregate means and variances.
4. Pseudonymization / Tokenization: Replacing direct identifiers with artificial identifiers (tokens/hashes). Note: Pseudonymization is reversible with a lookup key and is considered de-identification rather than full anonymization.

Privacy Models

1. $k$-Anonymity

A dataset satisfies $k$-anonymity if every combination of quasi-identifiers in the released table matches at least $k$ distinct individuals (an equivalence class of size $\ge k$).

• Example ($k=2$): A release where any (Age Group, Gender, ZIP) combination appears at least 2 times.

Limitations & Weaknesses of $k$-Anonymity

• Homogeneity Attack: If all $k$ records in an equivalence class share the same sensitive value (e.g., all 4 patients in an age/ZIP bucket have Flu), an attacker knows with 100% certainty the victim has Flu.
• Background Knowledge Attack: An attacker combining domain knowledge with $k$-anonymized data can narrow down possibilities (e.g., knowing an individual's diet or lifestyle can eliminate specific diagnoses).
• Vulnerable to High Dimensions: In datasets with many attributes ("curse of dimensionality"), achieving $k$-anonymity requires heavy data suppression, destroying utility.

2. $\ell$-Diversity

Extends $k$-anonymity by requiring that each equivalence class contains at least $\ell$ "well-represented" distinct values for each sensitive attribute.

• Fixes: Mitigates the homogeneity attack by ensuring diversity among sensitive values in each group.
• Limitations:
  • Skewness Attack: If a sensitive attribute is rare overall (e.g., 99% negative, 1% positive), forcing equal representation can distort real distributions.
  • Similarity Attack: If the $\ell$ sensitive values are semantically similar (e.g., Stomach Cancer, Colon Cancer, Gastric Ulcer), the attacker still learns the general condition.

3. $t$-Closeness

Extends $\ell$-diversity by requiring the distance between the distribution of a sensitive attribute within any equivalence class and the global distribution of that attribute in the entire dataset to be no more than a threshold $t$ (using Earth Mover's Distance).

• Benefit: Prevents attribute disclosure by preserving the natural background distribution across all groups.

4. Differential Privacy (DP)

Differential Privacy is the mathematical standard for privacy-preserving data analysis. An algorithm is $(\epsilon, \delta)$-differentially private if the presence or absence of any single individual's record does not significantly change the probability distribution of the query output.

$$\Pr[\mathcal{M}(D_1) \in S] \le e^\epsilon \cdot \Pr[\mathcal{M}(D_2) \in S] + \delta$$

Where:

• $D_1, D_2$ are neighboring datasets differing by at most one individual.
• $\epsilon$ (Privacy Budget): Controls the privacy-utility tradeoff. Smaller $\epsilon$ means stronger privacy but more added noise.
• $\delta$: Probability of failure (usually negligible, e.g., $\ll 1/|D|$).

Mechanisms

• Laplace Mechanism: Adds noise drawn from $\text{Laplace}(0, \Delta f / \epsilon)$ to numerical query results, where $\Delta f$ is the global $L_1$ sensitivity of the query function $f$.
• Gaussian Mechanism: Adds noise drawn from $\mathcal{N}(0, \sigma^2)$ for $(\epsilon, \delta)$-DP.
• Local DP vs. Global DP:
  • Global DP: Trusted curator adds noise to query results over the central dataset (e.g., US Census Bureau).
  • Local DP: Client/device perturbs data before sending it to the server (e.g., Apple iOS telemetry, Google RAPPOR).

Comparison Summary

Model	Primary Defense	Vulnerability / Drawback
$k$-Anonymity	Identity disclosure	Homogeneity attack, background knowledge
$\ell$-Diversity	Homogeneity attack	Skewness attack, semantic similarity attack
$t$-Closeness	Distribution-based inference	Loss of utility, complex to compute
Differential Privacy	Arbitrary auxiliary knowledge & reconstruction attacks	Requires noise tuning; complex for multi-dimensional queries