Re-identification Risk

The probability that an adversary can re-identify a specific, targeted individual within a de-identified dataset. This metric assumes the attacker possesses auxiliary information about the target and attempts to match it to a single record. Prosecutor risk is the most stringent measure because it focuses on the worst-case scenario for a known person. It is calculated by evaluating the uniqueness of quasi-identifier combinations and the attacker's background knowledge. A dataset with low prosecutor risk ensures that even if an adversary knows a target's zip code, age, and gender, they cannot isolate that person's record with high confidence.

The probability that an adversary can re-identify any single record in the dataset without targeting a specific individual beforehand. Unlike prosecutor risk, journalist risk models an attacker who attempts to breach the dataset and find at least one vulnerable record. This is a population-to-sample attack where the adversary tries to link any record to a known individual. It is generally higher than prosecutor risk because the attacker can exploit the most unique records. Mitigation involves ensuring no equivalence class is too small, typically enforced through k-anonymity constraints.

The probability that an adversary can re-identify a substantial proportion of records in the dataset. Marketer risk models an attacker whose goal is mass re-identification for commercial gain, such as linking a de-identified medical database to a marketing list. This metric evaluates the overall vulnerability of the dataset rather than individual records. It is measured by the expected number of correct record linkages across the entire dataset. Defenses include l-diversity and t-closeness to prevent attribute disclosure even when re-identification succeeds.

Quantitative measures of how distinguishable records are within a dataset based on quasi-identifiers. Key metrics include:

• Uniqueness Ratio: The fraction of records that are unique in the population given a set of quasi-identifiers
• Correct Attribution Probability (CAP): The likelihood that an attacker correctly links a de-identified record to the true individual
• Record Linkage Success Rate: The percentage of records successfully matched to an external identified dataset using deterministic or probabilistic linkage These metrics are computed empirically by simulating attacks using auxiliary datasets or through theoretical population uniqueness models.

Privacy metrics grounded in information theory that quantify the reduction in uncertainty about an individual's data after observing a release. Mutual information measures the dependency between the original sensitive data and the released output. Min-entropy leakage captures the worst-case probability of guessing a secret given the release. Differential privacy's epsilon formalizes the maximum information leakage as a multiplicative bound on output probabilities. These measures provide provable guarantees independent of attacker background knowledge, making them the gold standard for formal privacy accounting.

A practical methodology for measuring re-identification risk by executing controlled attacks against a de-identified dataset. The process involves:

• Assembling an auxiliary dataset representing realistic attacker knowledge
• Executing record linkage algorithms (deterministic and probabilistic) to match records
• Computing precision, recall, and F1-score of the linkage
• Iterating with varying quasi-identifier subsets to identify the most vulnerable attribute combinations This empirical approach complements theoretical metrics and is required under Expert Determination for HIPAA Safe Harbor compliance.

Researchers Arvind Narayanan and Vitaly Shmatikov demonstrated a linkage attack by cross-referencing the anonymized Netflix movie ratings dataset with publicly available IMDb reviews. Using only ratings and dates as quasi-identifiers, they successfully identified individual users and inferred their political affiliations and other sensitive preferences. The attack exploited the sparsity and uniqueness of individual rating patterns, proving that removing direct identifiers is insufficient when auxiliary data exists.

AOL Research released 20 million search queries from 650,000 users, replacing usernames with numeric IDs. Within days, journalists from the New York Times successfully re-identified specific individuals by analyzing the semantic content of search histories. User 4417749 was traced to Thelma Arnold in Lilburn, Georgia, simply by searching for local businesses, personal names, and health conditions. This incident highlighted that unstructured text contains rich quasi-identifier information.

Latanya Sweeney famously re-identified the medical records of Massachusetts Governor William Weld from an anonymized state employee health insurance dataset. By purchasing the Cambridge voter registration rolls for $20, she linked the ZIP code, birth date, and sex present in both datasets. This foundational case proved that 87% of the U.S. population is uniquely identifiable using only these three quasi-identifiers, directly motivating the development of k-anonymity.

The NYC TLC released a dataset of 173 million taxi trips with medallion numbers hashed using MD5. Researchers reversed the anonymization by exploiting the small input domain of medallion numbers and the deterministic nature of unsalted hashing. Combined with pickup/drop-off coordinates and timestamps, they identified specific drivers, calculated their incomes, and even reconstructed trips to strip clubs and celebrity residences, exposing the failure of naive pseudonymization.

Fitness app Strava published a global heatmap visualizing 3 trillion GPS points from user activities. Analysts quickly identified the outlines of secret military bases in Syria, Afghanistan, and Djibouti, as soldiers using fitness trackers revealed patrol routes and base perimeters. The spatial aggregation intended to anonymize the data instead highlighted anomalous activity patterns in otherwise dark zones, demonstrating that location data is inherently identifying even in aggregate.

Researchers from the University of Melbourne successfully re-identified individuals in an open dataset of Australian Medicare Benefits Schedule and Pharmaceutical Benefits Scheme records. Despite encryption of patient IDs, the longitudinal nature of the data—linking medical services and prescriptions over time—created unique clinical fingerprints. By chaining rare medical events and provider visits, they demonstrated that temporal patterns in medical histories serve as powerful quasi-identifiers.

A foundational privacy model ensuring each record is indistinguishable from at least k-1 other records based on quasi-identifiers (QIDs). It prevents singling out attacks by forcing equivalence classes of size k. However, it is vulnerable to homogeneity attacks if sensitive attributes lack diversity within a group, and background knowledge attacks from external data linkage.

An extension of k-anonymity that defends against homogeneity attacks. It requires each k-anonymous equivalence class to contain at least l 'well-represented' values for sensitive attributes. Variants include:

• Distinct l-diversity: Ensures l distinct sensitive values per class.
• Entropy l-diversity: Requires the entropy of sensitive values to exceed a threshold.
• Recursive (c,l)-diversity: Limits the frequency of the most common value.

A refinement of l-diversity that prevents skewness attacks and similarity attacks. It mandates that the distribution of a sensitive attribute in any equivalence class must be within a threshold t of its global distribution in the entire dataset, measured using Earth Mover's Distance. This limits an attacker's ability to infer new information about an individual beyond the population baseline.

A mathematical framework providing a provable guarantee against re-identification. It ensures the output of a query is statistically indistinguishable whether or not any single individual is in the dataset. Controlled by the epsilon (ε) privacy budget, it injects calibrated noise via mechanisms like Laplace or Gaussian distributions. It is the gold standard for resisting linkage attacks using arbitrary auxiliary information.

A specific re-identification attack where an adversary determines if a known individual's record was used to train a machine learning model. By analyzing prediction confidence scores, loss values, or shadow models, attackers exploit overfitting to leak training set membership. Defenses include differential privacy during training, knowledge distillation, and adversarial regularization to reduce the gap between training and non-training data outputs.

A practical suite of methods to reduce re-identification risk in microdata and tabular data releases. Techniques include:

• Data Perturbation: Adding noise, rounding, or rank swapping.
• Suppression: Removing high-risk cells or attributes.
• Generalization: Recoding specific values into broader categories (e.g., exact age to age range). SDC balances information loss against disclosure risk.