Re-Identification Risk

The primary mechanism enabling re-identification is the presence of quasi-identifiers—attributes like date of birth, gender, and ZIP code that are not unique on their own but become identifying in combination. Record linkage attacks cross-reference these attributes against external datasets, such as voter registration records or commercial databases, to resolve identities. The uniqueness of a record in a population is the critical metric; research shows 87% of the U.S. population is uniquely identifiable using only 5-digit ZIP, gender, and date of birth.

Re-identification risk scales directly with the volume and granularity of auxiliary data available to an attacker. This includes public records, social media profiles, data broker dossiers, and previously leaked datasets. The information mosaic effect describes how adversaries aggregate non-sensitive data points from disparate sources to construct a comprehensive identity profile. A dataset that appears anonymous in isolation becomes high-risk when contextualized within the broader data ecosystem.

The mathematical rigor of the de-identification method directly determines risk. K-anonymity ensures each record is indistinguishable from at least k-1 others but remains vulnerable to homogeneity and background knowledge attacks. Differential privacy provides a provable guarantee by injecting calibrated noise, bounded by the epsilon parameter (privacy budget). A lower epsilon means stronger privacy but reduced data utility. The absence of a formal privacy model leaves datasets vulnerable to singling out and inference attacks.

Technical de-identification is necessary but insufficient without binding legal controls. Data use agreements must prohibit re-identification attempts, and purpose limitation clauses restrict the context in which data can be processed. The Health Insurance Portability and Accountability Act (HIPAA) Safe Harbor method requires removal of 18 specific identifiers, while the EU General Data Protection Regulation (GDPR) adopts a risk-based approach considering the costs, time, and technology available for re-identification. Weak contractual enforcement elevates residual risk.

Re-identification risk is not static over time. Data staleness can reduce risk as records become outdated, but conversely, the accumulation of auxiliary data over time increases the attack surface. New public datasets, advances in machine learning inference, and the proliferation of high-dimensional data (e.g., genomic sequences, location trajectories) can render previously safe anonymization techniques obsolete. Continuous risk assessment is required to account for the evolving threat landscape.

Combining multiple de-identified datasets can create a composition effect where the aggregate information reveals more than the sum of its parts. Attributes that are non-identifying in one dataset may become quasi-identifiers when joined with another. This is particularly acute in data lake and data mesh architectures where cross-domain linkage is a design feature. Preventing re-identification requires controlling not just individual dataset release but the cumulative information disclosed across all releases.

A data de-identification technique that replaces direct identifiers (name, email, SSN) with artificial pseudonyms or tokens.

• Data remains linkable for analysis but not directly attributable without additional information
• Differs from anonymization: pseudonymized data is still considered personal data under GDPR
• Re-identification risk persists if the mapping table or additional attributes are compromised
• Often implemented via tokenization or cryptographic hashing with salt

A privacy model ensuring that each record is indistinguishable from at least k-1 other records with respect to quasi-identifiers.

• Protects against identity disclosure but remains vulnerable to homogeneity and background knowledge attacks
• Implemented through generalization (replacing specific values with ranges) and suppression (removing outlier records)
• A dataset with k=5 means any individual's record is hidden within a group of at least 5 similar records
• Limitations: does not protect against attribute disclosure when sensitive values are homogeneous within a group

An extension of k-anonymity that requires each equivalence class to contain at least l well-represented sensitive values.

• Addresses the homogeneity attack weakness of k-anonymity
• Distinct l-diversity ensures at least l different sensitive values per group
• Entropy l-diversity requires the entropy of sensitive value distribution to exceed a threshold
• Example: In a medical dataset, each anonymized group must contain patients with at least 3 different diagnoses

A privacy model requiring that the distribution of a sensitive attribute in any equivalence class is within a threshold t of its distribution in the overall dataset.

• Prevents skewness attacks where an attacker learns that an individual's sensitive value is statistically rare
• Uses Earth Mover's Distance (EMD) to measure the difference between distributions
• More robust than l-diversity against probabilistic inference attacks
• Example: If 5% of the overall population has a rare disease, no anonymized group should have a significantly higher or lower proportion

A re-identification technique where an attacker cross-references a de-identified dataset with external, publicly available datasets using shared attributes.

• The most famous example: researchers re-identified the Netflix Prize dataset by linking it with IMDb public reviews
• Quasi-identifiers like zip code, birth date, and gender are commonly exploited
• Governor William Weld's medical records were re-identified from anonymized health data using voter registration records
• Mitigation requires understanding the unicity of combinations of quasi-identifiers in the target population