k-Anonymity

Quasi-identifiers are attributes that do not uniquely identify an individual alone but can do so when linked with external datasets—such as zip code, date of birth, and gender. k-anonymity protects against linking attacks by ensuring that any combination of quasi-identifiers in the released dataset appears at least k times.

• Example: In a medical dataset, the triplet (ZIP=02138, DOB=1975-03-12, Sex=F) must appear at least k times
• Sweeney's landmark 2000 study showed 87% of the U.S. population is uniquely identifiable using only these three attributes
• The model assumes the data curator can correctly identify all quasi-identifiers before release

Generalization replaces specific quasi-identifier values with broader, less precise categories to achieve the k-anonymity threshold. Values are transformed according to a predefined domain generalization hierarchy (DGH) that maps specific values to increasingly abstract representations.

• ZIP code 02138 → 0213* → 021** → 02*** → 0****
• Age 34 → age range 30-39 → 30-49 → 20-59
• The optimal generalization strategy minimizes information loss while satisfying the k constraint
• Over-generalization can render data analytically useless—a critical trade-off in healthcare applications

Suppression (or cell suppression) removes outlier records or specific attribute values that cannot be generalized to meet the k threshold without excessive information loss. This is applied when a record's quasi-identifier combination is so rare that even aggressive generalization fails to create an equivalence class of size k.

• Outlier records with rare disease profiles may require complete suppression
• Suppression rate is a key metric: the percentage of records removed to achieve k-anonymity
• Excessive suppression introduces selection bias and reduces statistical utility
• Typically used as a last resort after generalization options are exhausted

An equivalence class is a set of records that share identical quasi-identifier values after generalization and suppression. The core requirement of k-anonymity is that every equivalence class in the released dataset contains at least k records.

• If k=5, every unique quasi-identifier combination must map to 5 or more individuals
• An attacker attempting to re-identify a target can only narrow them down to the equivalence class, never to a single record
• The minimum equivalence class size directly equals the k parameter
• Homogeneous equivalence classes with identical sensitive attributes still leak information—a limitation addressed by l-diversity

k-anonymity does not protect against homogeneity attacks—scenarios where all records in an equivalence class share the same sensitive attribute value. If an attacker knows a target belongs to a specific equivalence class, they immediately learn the sensitive value despite k-anonymity protection.

• Example: All k=10 records in a ZIP=0213* equivalence class have HIV=positive
• The attacker learns the target's HIV status without needing to distinguish between the 10 records
• This limitation motivated the development of l-diversity (requiring at least l distinct sensitive values per class)
• Further refined by t-closeness (requiring the sensitive value distribution to match the overall population)

k-anonymity is vulnerable to background knowledge attacks where an adversary uses external information to probabilistically eliminate records within an equivalence class. Even when k records are indistinguishable by quasi-identifiers, auxiliary knowledge can break the anonymity guarantee.

• An attacker knows the target is not Japanese; if k-1 records in the class are Japanese, the target is uniquely identified
• This attack vector led to extensions like l-diversity and t-closeness
• The model assumes the data curator cannot anticipate all possible external knowledge an adversary may possess
• Practical mitigation requires conservative k values and careful sensitive attribute handling

A data de-identification technique that replaces direct identifiers (names, medical record numbers) with artificial pseudonyms or tokens. The mapping between pseudonyms and original identities is stored separately and protected by technical and organizational controls.

• Data remains re-identifiable under controlled conditions
• Retains analytical utility better than full anonymization
• Required under GDPR as a technical safeguard

The irreversible process of transforming personal data so the data subject can no longer be identified by any means reasonably likely to be used. Once properly anonymized, data falls outside the scope of GDPR and HIPAA.

• Must resist singling out, linkability, and inference
• k-anonymity is one formal model for achieving this
• True anonymization is increasingly difficult with high-dimensional data

An adversarial attack that determines whether a specific individual's record was present in a model's training dataset. This directly threatens the privacy guarantees k-anonymity aims to provide.

• Exploits differences in model confidence between seen and unseen data
• Particularly dangerous for genomic and rare disease datasets
• Mitigated by differential privacy and knowledge distillation

An attack that reconstructs representative training samples or sensitive attributes by exploiting access to a trained model's outputs or gradients. Even k-anonymized datasets used for training can leak information through the model itself.

• Can reconstruct facial images from facial recognition models
• Exploits confidence scores and class logits
• Defended against with gradient clipping and differential privacy

A cryptographic protocol in federated learning that computes the sum of model updates from multiple clients while ensuring the central server learns only the aggregated result, not any individual contribution.

• Uses secret sharing and pairwise masking
• Complements k-anonymity at the computation layer
• Prevents gradient leakage during model training