TL;DR
This paper reveals a significant privacy risk in common patient matching techniques (PPRL) when hashed patient identifiers are shared alongside basic demographic information. They demonstrate a practical attack that can re-identify a substantial portion of individuals in large datasets, highlighting that current PPRL strategies are not as secure as often assumed at scale. Fortunately, the authors also show that this risk is avoidable through careful token design and implementation.
What Problem Does This Paper Address?
Healthcare organizations and researchers often need to link patient records across different datasets to gain a comprehensive view of patient journeys for research or disease surveillance. However, directly sharing personally identifiable information (PII) is a privacy and legal concern. Privacy-Preserving Record Linkage (PPRL) techniques aim to solve this by transforming direct identifiers (like names and dates of birth) into encoded "tokens" before sharing. The idea is that these tokens, when combined with de-identified demographic data (like age, race, or ZIP code), allow for accurate record matching without revealing individual identities.
The problem this paper addresses is that while PPRL is increasingly used at large scales (state or national level), the privacy guarantees of these methods, especially when combined with commonly shared de-identified demographics, haven't been fully reassessed. The authors investigate whether a specific attack, leveraging the combination of hashed tokens and demographic data, poses a significant re-identification risk, particularly as datasets grow larger.
Methods
The core of the paper is a novel re-identification attack that exploits the repetition of PPRL tokens and the availability of common demographic information. The attack proceeds in several steps:
- Grouping: Records with the same token are grouped together.
- Fingerprinting: For each token group, a "fingerprint" is created using the demographic information associated with the individuals in that group. This fingerprint is essentially a list of demographic values.
- Matching: The fingerprints from the de-identified dataset are compared against fingerprints generated from a reference dataset of identified individuals. If a fingerprint uniquely matches between the two datasets, the token can be "unblinded."
- Identification: Once a token is unblinded, it can be linked to the corresponding identified individual in the reference dataset.
The authors also extend this attack to scenarios where multiple tokens are used per patient, noting that while this can improve linkage accuracy, it can also amplify re-identification risks. They simulate this by creating combined fingerprints from multiple tokens and associated demographics.
Datasets
The study uses publicly available voter registration lists from Florida, North Carolina, and Ohio. These datasets were used to create a reference database of identified individuals. For experimental purposes, they synthesized a portion of the North Carolina data and generated synthetic datasets representing millions of individuals to simulate large-scale scenarios. The reference set contained approximately 30.9 million individuals.
Key Insights and Ideas
- The "Demographic + Token" Combination is the Vulnerability: The attack isn't solely about the tokens themselves or the demographics in isolation, but the combination of repeated tokens with shared demographic data that creates the re-identification risk.
- Scale is the Great Enabler: While the re-identification risk is minimal for small datasets (under a million individuals), it escalates dramatically as the population size increases, becoming a serious concern for national-scale data linkage.
- Token Design Matters Immensely: Not all PPRL strategies are equally vulnerable. Tokens that are more unique and less prone to repetition (e.g., those combining more specific attributes like full names and dates of birth) offer much better protection.
- Multiple Tokens Can Backfire: Using multiple tokens per patient, a common strategy to improve linkage accuracy, can paradoxically increase re-identification risk by providing more "fingerprinting" opportunities.
- Mitigation is Achievable: The risk is not inherent to PPRL but stems from specific implementation choices. Strategies like using better-designed tokens or employing a trusted third party for matching (decoupling tokens from demographics) can effectively eliminate this risk.
Key Results
- For common tokenization strategies, re-identification risk is typically under 1% for datasets with fewer than one million individuals.
- At national scales (e.g., 250 million individuals), this risk can jump to 10%-20% for commonly used tokens.
- Token C, which uses ZIP3 instead of date of birth, showed significantly higher re-identification rates, reaching over 45% even in smaller datasets, due to the coarseness of ZIP3 codes.
- Token D, which combined full names with date of birth and full ZIP code, demonstrated the lowest re-identification rates, suggesting that highly specific tokens can preserve privacy even at large scales.
- Removing "year of birth" from the fingerprinting process significantly increased re-identification risk, highlighting its importance in disambiguation.
Limitations and Future Work
- Dataset Limitations: The experimental data was based on voter registration lists, which represent a subset of the adult population and may not perfectly reflect the demographic distributions or latent correlations found in healthcare datasets (especially those including minors). Future work should account for these potential representation biases.
- Unbiased Sampling Assumption: The study assumes healthcare datasets are unbiased samples of the national population. Real-world datasets are often biased, and future work should explore how these biases affect re-identification risk.
- Future Work: The authors suggest exploring more robust tokenization strategies, investigating the impact of latent demographic signals (like socioeconomic status) on privacy risk, and further developing mitigation strategies such as centralized matching architectures and careful token design.
Summary updated