Simulating how "de-identified" health records collapse back to named individuals — Safe Harbor, Expert Determination, and quasi-identifier linkage attacks
Under the HIPAA Privacy Rule, 45 CFR §164.514(b)(2), a covered entity may declare health information "de-identified" simply by removing 18 enumerated categories of identifiers and having no actual knowledge that the remaining information could identify an individual. It is the most widely used de-identification method in U.S. healthcare because it requires no statistician — just a checklist.
The full list a covered entity must remove: (1) names; (2) all geographic subdivisions smaller than a state, including street address, city, county, and the initial 3 digits of ZIP if the associated area has ≤20,000 people; (3) all elements of dates (except year) directly related to an individual — birth date, admission date, discharge date, death date — and all ages over 89 collapsed into "90 or older"; (4) telephone numbers; (5) fax numbers; (6) email addresses; (7) Social Security numbers; (8) medical record numbers; (9) health plan beneficiary numbers; (10) account numbers; (11) certificate/license numbers; (12) vehicle identifiers including license plates; (13) device identifiers and serial numbers; (14) URLs; (15) IP addresses; (16) biometric identifiers (finger and voice prints); (17) full-face photographs and comparable images; (18) any other unique identifying number, characteristic, or code.
The rule is deliberately mechanical: no statistical judgment is required, which is exactly why it under-protects against linkage attacks that use fields Safe Harbor never touches — sex, race, admission month, diagnosis, procedure codes, and 3-digit ZIP.
Safe Harbor is a checklist, not a risk calculation. It contains no requirement to model an adversary, compute population uniqueness, or verify that the surviving fields are jointly rare. A dataset can pass Safe Harbor and still contain a patient who is the only person of their sex in a sparsely populated 3-digit ZIP admitted with a rare diagnosis in a given year — trivially re-identifiable to anyone who knows that person was hospitalized that year.
The rule also excludes "limited data sets" (which retain dates and full geography) and permits re-identification by the covered entity itself via a coded, non-derivable re-identification key retained separately — a mechanism that itself has to be secured to prevent it from becoming the weak link.
| Product | Indication | Trial Design | Key Result |
|---|---|---|---|
| Safe Harbor | General-purpose release | Remove 18 enumerated identifier categories; no statistical test required | Fast, cheap, no expert needed |
| Expert Determination | Research datasets with rich fields | Qualified expert applies statistical methods to certify "very small" re-id risk | Preserves more analytic utility |
| Limited Data Set + DUA | Research/public-health partners | Retains dates & full geography under a signed data use agreement | Keeps temporal/spatial detail |
| k-Anonymity / Differential Privacy | Public microdata & statistical releases | Formal generalization or calibrated noise with provable bounds | Mathematically quantifiable risk |
The alternative HIPAA pathway, 45 CFR §164.514(b)(1), lets a person with "appropriate knowledge of and experience with generally accepted statistical and scientific principles" certify that the risk a dataset could be used, alone or combined with other reasonably available information, to identify an individual is "very small." Unlike Safe Harbor, this method actually measures risk.
A typical statistical disclosure control workflow, following Khaled El Emam's widely used framework:
1. Identify every quasi-identifier in the dataset — fields not on the Safe Harbor list but jointly identifying: sex, 3-digit ZIP, birth year, admission month, rare diagnosis, employer, marital status. 2. Define the plausible adversary: a "prosecutor" who already suspects a specific person is in the data, a "journalist" attempting to identify anyone, or a "marketer" seeking to match many records at once. 3. Compute population-to-sample uniqueness — for each equivalence class of matching quasi-identifier values, how many people in the real-world population (not just the sample) share those values? 4. Apply generalization, suppression, or noise until every class meets the target risk threshold (commonly k≥5 or an 0.09–0.2 probability-of-correct-match ceiling used by statistical agencies). 5. Conduct a "motivated intruder" test — have an independent tester with only public resources and reasonable effort attempt re-identification, a method the UK Information Commissioner's Office formally requires. 6. Document the analysis, assumptions, and expiration — re-assessment is recommended roughly annually as auxiliary datasets (voter rolls, obituaries, social media) keep growing.
El Emam's 2011 systematic review, "A Systematic Review of Re-identification Attacks on Health Data" (PLOS ONE), examined 14 published re-identification demonstrations against data that had been de-identified. Datasets processed with a defensible statistical methodology showed a median successful re-identification rate of just 0.013% of records. But datasets de-identified with weak, informal, or Safe-Harbor-only approaches saw re-identification rates as high as 100% in some demonstrations — the gap between "removed the 18 fields" and "actually modeled the adversary" is enormous.
In 1997, Latanya Sweeney, then an MIT graduate student, showed that three ordinary demographic fields — 5-digit ZIP code, full date of birth, and sex — uniquely identify the overwhelming majority of the U.S. population when joined against a public voter registration list. The finding reshaped health-privacy law and remains the canonical linkage attack.
Massachusetts's Group Insurance Commission (GIC) released hospital visit summaries for roughly 135,000 state employees to researchers, believing the data was safe because names, addresses, and Social Security numbers had been removed — a Safe-Harbor-style pass. The records still carried ZIP code, birth date, and sex, plus diagnosis and visit dates.
Sweeney paid $20 for the full Cambridge, Massachusetts voter registration list, which openly lists name, address, ZIP, birth date, and sex — a legal public record in most U.S. states. Joining the two files on ZIP + birth date + sex, she found that only six people in Cambridge shared then-Governor William Weld's birth date; of those, only three were men; and only one of those three lived in his ZIP code. That one record was his — and it included his diagnoses and prescriptions. She mailed the "de-identified" record to his office to make the point.
The combinatorics explain the result. A U.S. ZIP code space spans roughly 33,000 codes, a birth date spans about 365×100 ≈ 36,500 possible values across a lifetime, and sex is binary — a nominal state space in the tens of millions of combinations, far larger than the population of any single ZIP code. Because population is unevenly distributed across ZIP × birth date × sex combinations, most people fall into equivalence classes of size one: nobody else in the data shares all three values.
Golle's 2006 replication using complete 2000 U.S. Census summary files (rather than the older 1990 data Sweeney used) found a slightly lower but still striking 63% unique-identification rate and 87–100% for narrower subpopulations — the qualitative conclusion held even as the exact percentage shifted with the reference year.
Under the modern Safe Harbor rule, full ZIP and exact birth date would themselves have to be removed — precisely because of the Weld case. But 3-digit ZIP plus birth year plus sex, all still permitted by Safe Harbor, remains linkable to increasingly rich auxiliary data: obituaries confirm death dates, social media posts confirm ZIP and age, and public court, property, or professional-license records add still more corroborating fields, gradually reconstructing the fine-grained quasi-identifier set Safe Harbor tried to erase.
Sweeney formalized the lesson of the Weld case into k-anonymity (Sweeney, 2002, International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems): a dataset satisfies k-anonymity if every combination of quasi-identifier values shared by any record is shared by at least k−1 other records. No individual can be distinguished from at least k−1 others based on the quasi-identifiers alone.
k-anonymity is achieved by two operations applied to quasi-identifiers until every equivalence class reaches size ≥ k:
• Generalization: replace a precise value with a broader category — a 5-digit ZIP becomes a 3-digit ZIP, then a state; an exact birth date becomes a birth year, then a 5-year age band; a specific diagnosis code becomes a diagnosis category. • Suppression: remove or blank outlier records entirely when generalizing them enough to reach k would destroy too much data utility — usually capped at a small suppression budget (e.g., <5% of rows).
Algorithms like Datafly (Sweeney, 1998), Incognito, and Mondrian search the generalization lattice automatically, finding the minimal amount of generalization needed to hit a target k while maximizing remaining data usefulness — a direct trade-off between privacy and analytic precision that every de-identification project must navigate explicitly rather than leaving to a fixed checklist.
k-anonymity only constrains identity disclosure, not attribute disclosure. In a homogeneity attack, if every one of the k records in a class shares the same sensitive value (e.g., all k patients in a ZIP/age class have the same rare diagnosis), an adversary who narrows a target to that class learns the diagnosis with certainty even without knowing which specific record is theirs. Machanavajjhala et al.'s 2006 l-diversity requires each equivalence class to contain at least l well-represented sensitive values, and Li et al.'s 2007 t-closeness further requires the class's sensitive-attribute distribution to resemble the overall dataset's distribution.
All three (k-anonymity, l-diversity, t-closeness) remain syntactic — they assume a fixed, enumerable set of quasi-identifiers and a bounded adversary. Differential privacy, formalized by Dwork et al. in 2006, instead gives a mathematical guarantee that holds regardless of what auxiliary data an adversary might possess, by bounding how much any single individual's presence in the dataset can change the probability of any output.
Every major "anonymized" data release of the last two decades has been met with a re-identification demonstration within months to years. The pattern is consistent: the data holder underestimates available auxiliary information. The modern response is a shift from heuristic anonymization toward differential privacy — a mathematically provable bound on individual disclosure risk.
In August 2006, AOL Research publicly released 20 million search queries from 657,000 users, replacing usernames with numeric IDs — a naive anonymization that ignored the fact that search queries themselves are quasi-identifiers. New York Times reporters Michael Barbaro and Tom Zeller traced user "No. 4417749" through queries like "homes sold in [her town]" and "landscapers in [her town]" to Thelma Arnold, a 62-year-old widow in Lilburn, Georgia, within days. AOL pulled the data, fired the responsible researcher, and its CTO resigned; an FTC complaint followed.
Netflix released 100 million anonymized movie ratings for its 2006 Netflix Prize, again replacing names with IDs. Arvind Narayanan and Vitaly Shmatikov (2008, "Robust De-anonymization of Large Sparse Datasets") showed that cross-referencing a handful of ratings and approximate dates against public IMDb reviews was enough to re-identify specific subscribers, including revealing a closeted lesbian mother's viewing history in a subsequent FTC/Doe v. Netflix lawsuit. Netflix cancelled its planned second competition in 2010.
Consumer DNA services (23andMe, AncestryDNA) let users export raw genotype data and upload it to third-party genealogy databases like GEDmatch. Law enforcement adopted this "investigative genetic genealogy" (IGG) to identify suspects from crime-scene DNA by finding distant relatives in these databases and building family trees — most famously the 2018 arrest of the Golden State Killer suspect after decades unsolved. More than 200 cold cases have been resolved via IGG since 2018.
Yaniv Erlich and colleagues (Science, 2018) calculated that a database covering just 2% of a target population is enough to find a third-cousin-or-closer match for roughly 99% of people of that ancestry, and estimated that ~60% of Americans of European descent were already identifiable this way in 2018 — a number that only grows as databases expand, meaning genetic anonymity is now effectively unattainable for most of that population regardless of whether they personally ever took a test.
Differential privacy (Dwork, McSherry, Nissim & Smith, 2006) adds carefully calibrated statistical noise to query outputs or published statistics so that the presence or absence of any single individual in the dataset changes the probability of any released result by at most a factor of e^ε — a formal, worst-case guarantee that does not depend on guessing what auxiliary data an attacker might have, unlike k-anonymity.
The U.S. Census Bureau adopted differential privacy for the 2020 Census via its TopDown Algorithm, with a total privacy-loss budget of ε = 19.61 allocated across geographic levels — a controversial trade-off that injected noise into small-area counts, prompting objections from redistricting analysts and some state demographers over accuracy at the block level. Apple and Google have deployed differential privacy in iOS/Android telemetry and Chrome usage statistics since the mid-2010s, showing the model scaling from Census-style batch releases to real-time aggregate collection.