Tokenization and Privacy-Preserving Record Linkage

Almost every interesting real-world question now spans datasets that no single custodian holds: pharmacy and medical claims know what was paid for, the EHR knows labs and vitals, a death index knows the fact and date of death, and SDOH vendors know neighborhood and area-level deprivation. Joining them on a person requires identifiers, but the whole US privacy regime (HIPAA) is built to stop clear-text identifiers from being shipped between parties. Tokenization resolves the tension: each party runs the same deterministic, salted, one-way hashing recipe over standardized identifiers (name, date of birth, sex, sometimes a partial SSN or address) to produce an irreversible token. Two records that hashed to the same token belong to the same person; nobody had to send a name.

The HIPAA de-identification logic is usually expert determination - a qualified statistician certifies that the token plus the retained data carry a very small re-identification risk - rather than the Safe Harbor checklist, because linkage needs a stable cross-dataset key that Safe Harbor would strip.

What actually happens in the US ecosystem

A token vendor (Datavant, HealthVerity, and similar) defines several token "recipes," each over a different identifier bundle, so that a missing or mistyped field in one recipe can be rescued by another. Crucially, tokens are site-keyed (encrypted again with a key unique to each data partner) so the same person carries a different token at site A than at site B; an honest broker holds a crosswalk that re-encrypts site A tokens into site B's space so the join can happen without either side learning the other's raw token. Deterministic linkage then joins on exact token equality.

Probabilistic / Bloom-filter PPRL

is the fuzzier cousin: each identifier is split into character n-grams and hashed into a bit vector (a Bloom filter); two vectors are compared by set-overlap similarity (Dice/Jaccard), so near matches - a hyphenated surname, a transposed birth month - still link with a calibrated threshold. Bloom-filter PPRL is what makes privacy-preserving probabilistic matching possible at all (Schnell, Bachteler, Reiher 2009).

Pros, cons, and trade-offs

(specific and comparative).

• vs direct-identifier (clear-text) deterministic linkage: Tokenization buys you a legally shippable key and a defensible de-identification posture; the cost is that you can no longer eyeball or hand-adjudicate a borderline pair, you inherit whatever the vendor's identifier standardization did, and an exact-token join is brittle to the very typos a human reviewer would have forgiven. Prefer clear-text linkage only inside a single custodian or an honest-broker enclave where PHI exchange is permitted; prefer tokenization the moment data crosses organizational boundaries.
• vs probabilistic / Bloom-filter PPRL within tokenization: A single deterministic token is precise (few false matches) but unforgiving (more false misses when identifiers are imperfect). A multi-token waterfall - try the strongest recipe, then fall back to weaker recipes for the unmatched - raises the match rate but each weaker recipe trades precision for recall, so false matches creep in on the rescued records. Bloom-filter PPRL recovers even more true pairs but needs threshold tuning and a small clerically reviewed or gold-standard sample to set the cut. Prefer deterministic-only when a false link is more damaging than a missed one (e.g., attributing a death to the wrong patient); prefer a waterfall or PPRL when coverage of the linkable population is the binding constraint.
• vs treating "linked" as a clean merge: The seductive error is to link, drop the unmatched, and analyze the linked cohort as if it were the source cohort. Linkage is a measurement with error in two directions and a selection mechanism, not a lossless join.

When NOT to use - and when it is actively misleading

• Do not report a linked analysis without a match rate and, where possible, false-match and false-miss estimates from a validation sample (a subset with a trusted gold-standard linkage). A 70% match rate silently discards 30% of the cohort; pretending the linked 70% is the whole cohort is the central trap.
• Selection bias from the linkable subpopulation. Whether a person links is not random. People with stable names and addresses, continuous insurance, and full identifiers link at much higher rates than mobile, younger, recently immigrated, or intermittently insured people - and those traits correlate with exposure and outcome. If you restrict to the linked subset, you are conditioning on linkage, which can open a collider path and bias the effect estimate. Report match rate by subgroup, compare linked vs unlinked on observed characteristics, and consider weighting (inverse-probability-of-linkage) or a sensitivity analysis.
• False matches contaminate the outcome. A wrong token link can graft another person's death or hospitalization onto your patient, biasing event rates in a direction that depends on the linkage error structure. Treat false matches like outcome misclassification, not like random noise.
• Do not assume Bloom-filter or token recipes are perfectly privacy-preserving; frequency and pattern attacks on Bloom filters exist, which is why salting, site-keying, and expert determination - not the hashing alone - carry the de-identification claim.

Data-source operational depth

• Claims: Identifiers come from enrollment/eligibility files; tokens are usually generated by the vendor on the closed-claims feed. Match rates are highest here because insurers maintain clean member identifiers, but Medicare Advantage and gaps in enrollment shrink the observable and therefore the linkable window.
• EHR: Identifiers can be messy (free-text names, missing SSN, registration typos), so EHR is where probabilistic/Bloom-filter PPRL earns its keep and where the multi-token waterfall recovers the most pairs.
• Registry / mortality: The death index (state files or a commercial composite) is the canonical reason to link; match quality here directly determines outcome ascertainment, so false matches and false misses must be quantified, not assumed.
• Linked (the deliverable): Reconcile token recipes across vendors, document which recipe matched each pair, carry a match-confidence field forward, and keep the unmatched records so match rate and selection can be audited downstream.

Decision diagram

flowchart TD
  Src[Source cohort record<br/>standardized identifiers] --> Hash[Hash with salted recipe<br/>-> irreversible token]
  Hash --> Det{Strong-recipe token<br/>exactly equals a<br/>target token?}
  Det -- Yes --> Matched[Linked - recipe A<br/>high confidence]
  Det -- No --> Fall{Weaker recipe or<br/>Bloom-filter similarity<br/>above threshold?}
  Fall -- Yes --> Rescued[Linked - recipe B / PPRL<br/>lower confidence<br/>false-match risk]
  Fall -- No --> Unmatched[Unmatched<br/>contributes to false misses<br/>and shrinks match rate]
  Matched --> Eval[Validation sample:<br/>match rate, false-match rate,<br/>false-miss rate, by subgroup]
  Rescued --> Eval
  Unmatched --> Eval

Worked example

Scenario

We have 1,000 patients in a claims cohort and want to link them to an external death index using tokens. We first try a strong token recipe, then run a weaker recipe on whoever is left (a waterfall), and we split the cohort into patients with stable identifiers and more mobile patients to see whether linkage is even across groups and how much linkage error the weak recipe adds.

Dataset

Cohort-level linkage counts an analyst would assemble from the matched and unmatched token output.

FIG. 1 — DESIGN TIMELINE

Steps

Result

Overall match rate after the waterfall = 880/1000 = 0.88, but about 6 of the rescued links are false matches and the stable subgroup linked at 0.90 versus 0.70 for the mobile subgroup - so analyzing only the linked patients over-represents stable-identifier people and risks selection bias.

Trade-offs

Runnable example

import pandas as pd

def linkage_quality(cohort: pd.DataFrame) -> dict:
    n = len(cohort)
    n_matched = int(cohort["matched"].sum())
    match_rate = n_matched / n

    # False match: linked but not actually the same person (precision failure).
    fm = int(((cohort["matched"]) & (~cohort["truly_same_person"])).sum())
    false_match_rate = fm / n_matched if n_matched else 0.0

    # False miss: truly the same person but left unmatched (recall failure).
    n_true = int(cohort["truly_same_person"].sum())
    miss = int(((~cohort["matched"]) & (cohort["truly_same_person"])).sum())
    false_miss_rate = miss / n_true if n_true else 0.0

    # Selection: match rate by subgroup exposes the linkable subpopulation.
    by_subgroup = (
        cohort.groupby("subgroup")["matched"].mean().round(3).to_dict()
    )

    # Records rescued only by the weak recipe carry the most false-match risk.
    weak = cohort[(cohort["matched"]) & (cohort["recipe"] == "B")]
    weak_false_match_rate = (
        float((~weak["truly_same_person"]).mean()) if len(weak) else 0.0
    )

    return {
        "n": n,
        "match_rate": round(match_rate, 3),
        "false_match_rate": round(false_match_rate, 3),
        "false_miss_rate": round(false_miss_rate, 3),
        "match_rate_by_subgroup": by_subgroup,
        "weak_recipe_false_match_rate": round(weak_false_match_rate, 3),
    }

library(data.table)

linkage_quality <- function(cohort) {
  setDT(cohort)
  n         <- nrow(cohort)
  n_matched <- sum(cohort$matched)
  n_true    <- sum(cohort$truly_same_person)

  match_rate <- n_matched / n
  fm   <- sum(cohort$matched & !cohort$truly_same_person)
  miss <- sum(!cohort$matched & cohort$truly_same_person)
  false_match_rate <- if (n_matched > 0) fm / n_matched else 0
  false_miss_rate  <- if (n_true > 0)    miss / n_true  else 0

  by_subgroup <- cohort[, .(match_rate = round(mean(matched), 3)), by = subgroup]

  weak <- cohort[matched == TRUE & recipe == "B"]
  weak_false_match_rate <- if (nrow(weak) > 0)
    mean(!weak$truly_same_person) else 0

  list(
    n = n,
    match_rate = round(match_rate, 3),
    false_match_rate = round(false_match_rate, 3),
    false_miss_rate = round(false_miss_rate, 3),
    match_rate_by_subgroup = by_subgroup,
    weak_recipe_false_match_rate = round(weak_false_match_rate, 3)
  )
}

Citations

1. [1]Schnell R, Bachteler T, Reiher J. Privacy-preserving record linkage using Bloom filters. BMC Medical Informatics and Decision Making. 2009;9:41.
2. [2]Harron K, Dibben C, Boyd J, et al. Challenges in administrative data linkage for research. Big Data & Society. 2017;4(2):2053951717745678.

1. [3]Harron K, Gilbert R, Cromwell D, van der Meulen J. Utilising identifier error variation in linkage of large administrative data sources. BMC Medical Research Methodology. 2017;17:23.

1. [4]Bohensky MA, Jolley D, Sundararajan V, et al. Data linkage: a powerful research tool with potential problems. BMC Health Services Research. 2010;10:346.