Re-Identification Attack

The core mechanism relies on quasi-identifiers—attributes like ZIP code, birth date, and sex that are not unique on their own but become identifying when combined. An adversary joins a de-identified target dataset with a publicly available auxiliary dataset (e.g., voter registration records) on these shared attributes. Latanya Sweeney's foundational work demonstrated that 87% of the U.S. population is uniquely identifiable using only {5-digit ZIP, gender, date of birth}.

The attack's success depends entirely on the availability and granularity of external data sources. Adversaries leverage:

• Public records: Voter rolls, property tax databases, court filings
• Commercial data brokers: Aggregated purchasing history, demographic profiles
• Social media: Public profiles, check-ins, professional networks
• Data breaches: Previously leaked datasets containing direct identifiers The richer the auxiliary data ecosystem, the higher the probability of successful re-identification.

Re-identification attacks directly exploit failures in k-anonymity protections. A dataset satisfies k-anonymity when each record is indistinguishable from at least k-1 other records with respect to quasi-identifiers. Attacks succeed when:

• The chosen k-value is too low for the dataset's diversity
• Homogeneity attacks occur where sensitive attributes within an equivalence class are identical
• Background knowledge attacks leverage additional information the anonymization model did not account for

Multiple independently anonymized datasets can be cross-referenced to achieve re-identification even when each dataset individually appears safe. An adversary joins de-identified medical claims data with anonymized location pings and pseudonymous browsing logs. The intersection of quasi-identifiers across these sources creates a unique fingerprint that collapses anonymity. This attack vector is particularly dangerous in data marketplaces and research collaboratives where multiple sanitized views of the same population are released.

Quasi-identifiers exhibit temporal stability, meaning they remain linkable across time. A de-identified dataset released in 2020 can be re-identified using auxiliary data from 2023 because attributes like birth date, birthplace, and genetic markers do not change. Longitudinal studies and periodic data releases compound this risk—each release adds new quasi-identifier dimensions that adversaries can accumulate to progressively narrow anonymity sets over time.

In high-dimensional datasets with many attributes, nearly every record becomes unique due to the curse of dimensionality. Even when each attribute is coarsened or generalized, the combinatorial explosion of possible value combinations means most records occupy their own sparse region of the feature space. Adversaries exploit this by treating the full attribute vector as a high-resolution fingerprint, matching it against similarly rich auxiliary datasets where direct identifiers are present.

A foundational privacy property ensuring each released record is indistinguishable from at least k-1 other records with respect to quasi-identifier attributes. This prevents direct re-identification by forcing equivalence classes of size k.

• How it works: Generalization (replacing ZIP codes with regions) and suppression (removing outliers) are applied to quasi-identifiers.
• Critical limitation: K-anonymity does not protect against homogeneity attacks where all k records share the same sensitive value, or background knowledge attacks using external data.
• Example: A dataset where every combination of ZIP code, age, and gender appears at least 5 times achieves k=5 anonymity.

A data management procedure that replaces direct identifiers—such as names, email addresses, and social security numbers—with artificial pseudonyms or tokens. Unlike anonymization, pseudonymization is reversible with access to a separate mapping table.

• Re-identification risk: Pseudonymized data remains highly vulnerable when quasi-identifiers like date of birth, gender, and postal code are retained. The 2006 AOL search data leak demonstrated this when pseudonymized user IDs were re-identified using search query patterns.
• GDPR distinction: Pseudonymized data is still considered personal data under GDPR, while truly anonymized data falls outside regulatory scope.
• Best practice: Combine pseudonymization with differential privacy or k-anonymity to reduce linkability.

An attack that determines whether a specific data record was part of a machine learning model's training dataset by analyzing the model's prediction behavior. This directly threatens the privacy of individuals in sensitive datasets.

• Mechanism: Attackers train a shadow model on a similar dataset to learn the difference between predictions on training members versus non-members. The target model typically shows higher confidence on training data.
• Amplifying factors: Overfitting significantly increases vulnerability—models that memorize training data leak stronger membership signals.
• Real-world impact: Membership inference has been demonstrated against large language models, revealing whether specific documents or code repositories were used during pretraining.

An attack that infers sensitive attributes of individuals in a training dataset by exploiting correlations learned by the model and access to non-sensitive features. Unlike membership inference, this attack reconstructs the values of private attributes.

• Example: Given a model trained on medical records, an attacker with access to a patient's public demographic data can infer their genetic markers or disease status by observing how the model responds to queries.
• Correlation exploitation: The model learns statistical relationships between non-sensitive inputs and sensitive labels. Attackers reverse-engineer these correlations.
• Mitigation: Differential privacy during training and output perturbation can bound the leakage of attribute information.

A mathematical framework that provides provable privacy guarantees by adding calibrated noise to data or model outputs. The core principle: the removal or addition of a single record should not significantly change observable results.

• Epsilon (ε): The privacy budget parameter. Lower values indicate stronger privacy. ε=0 provides perfect privacy but zero utility; ε=1 is considered strong; ε=10 is weak.
• DP-SGD: Differentially Private Stochastic Gradient Descent clips per-sample gradients and adds Gaussian noise during training, providing DP guarantees for the final model.
• Composition: Privacy loss accumulates across queries. A privacy accountant tracks total ε consumption across all operations on a dataset.

A core privacy principle dictating that data collection and processing should be limited to what is strictly necessary for a specified purpose. This directly reduces the attack surface for re-identification and model inversion.

• Implementation strategies: Collect only essential fields, set aggressive retention schedules, and apply aggregation before storage when individual records are not required.
• Regulatory alignment: GDPR Article 5(1)(c) mandates data minimization as a binding legal requirement, not just a best practice.
• Privacy by design: Minimization should be architected into data pipelines from the start—retrofitting is expensive and often incomplete. Removing quasi-identifiers before storage eliminates re-identification risk at the source.