Privacy-Preserving Record Linkage

Before matching, quasi-identifiers (names, dates of birth, addresses) are transformed into irreversible, encoded representations.

• Bloom Filters: Bit arrays encoding q-gram sets of strings, enabling fast approximate matching via set similarity metrics like Dice coefficient.
• Phonetic Encoding: Algorithms like Soundex or Double Metaphone normalize linguistic variations in names before hashing.
• Field-level Hashing: HMAC with a secret key ensures deterministic encoding; without the key, reversing the hash is computationally infeasible.

This step ensures that even if the linkage unit is compromised, the original plaintext values remain protected.

PPRL protocols compute the similarity between encoded records without decoding them. This is the core mathematical challenge.

• Set-based Similarity: For Bloom filters, the Dice coefficient or Jaccard index calculates overlap between bit sets.
• Edit Distance Approximation: Techniques exist to estimate string edit distances directly on encoded q-gram representations.
• Homomorphic Encryption: Allows arithmetic operations on ciphertexts, enabling the calculation of dot products or Euclidean distances for numerical attributes while encrypted.

The protocol must balance computational efficiency with the accuracy of the similarity measure.

PPRL often involves three or more parties: two or more data custodians and a linkage unit. Secure Multi-Party Computation (SMPC) ensures no party learns anything beyond the final matching result.

• Commodity Server Model: A third party provides independent random numbers to mask data, preventing collusion attacks.
• Garbled Circuits: A cryptographic protocol where a function (the matching rule) is converted into a Boolean circuit and evaluated securely.
• Secret Sharing: Splitting encoded values into random shares distributed among parties; the original value is reconstructed only when shares are combined for the final match decision.

These protocols guarantee that the linkage unit sees only anonymous record pairs.

Comparing every record pair across databases is quadratically complex. PPRL uses privacy-preserving blocking to reduce the search space.

• Phonetic Blocking: Grouping records by Soundex codes of last names before encoding.
• Locality-Sensitive Hashing (LSH): Hashing encoded records into buckets such that similar items fall into the same bucket with high probability.
• Sorted Neighborhood: Sorting encoded records by a specific hash key and sliding a window to compare only nearby records.

Effective blocking dramatically reduces computational cost without significantly impacting recall.

A robust PPRL system must withstand active and passive adversaries. Threat models include:

• Frequency Attacks: An attacker with knowledge of plaintext frequency distributions attempts to re-identify encoded values by matching frequency histograms. Countermeasures include adding dummy records or frequency-hiding re-encoding.
• Dictionary Attacks: If the encoding key is compromised, an attacker can hash a dictionary of common names to reverse the mapping. Hardware Security Modules (HSMs) protect the key.
• Collusion Resistance: Protocols are designed so that even if the linkage unit colludes with one data custodian, they cannot learn the other custodian's private records.

Formal security proofs are essential for deployment in regulated environments.

The final step classifies encoded record pairs as matches or non-matches using privacy-preserving thresholds.

• Threshold-based Classification: A pair is a match if its encoded similarity score exceeds a calibrated threshold, often determined via differentially private parameter tuning.
• Hierarchical Clustering: For deduplication tasks, transitive closure is applied to matched pairs to form clusters representing unique entities.
• Manual Clerical Review: In high-stakes scenarios, a limited set of high-uncertainty pairs is sent to a trusted human reviewer through a secure, isolated channel.

The output is a mapping of anonymous entity identifiers, enabling data integration without identity disclosure.

Pharmaceutical companies and hospital networks use PPRL to identify patients eligible for trials across multiple institutions. Bloom filters encode patient identifiers (names, dates of birth) into privacy-preserving bit arrays. Matching is performed on the encrypted representations, allowing sponsors to find overlapping patient populations without any single hospital exposing its full patient registry. This accelerates recruitment while maintaining HIPAA and GDPR compliance.

Public health agencies link records from general practitioners, hospitals, and pathology labs to compile comprehensive cancer or rare disease registries. PPRL enables deterministic and probabilistic matching on encrypted quasi-identifiers. This allows epidemiologists to deduplicate patient counts and track disease incidence across a population without centralizing identifiable health data, a critical requirement under strict national data sovereignty laws.

Financial intelligence units and correspondent banks use PPRL to detect money laundering rings operating across jurisdictions. Secure multi-party computation (SMPC) protocols allow institutions to compare watchlists and transaction graphs to find common entities. The plaintext identities of customers are never revealed to foreign counterparties, satisfying strict bank secrecy laws while enabling collaborative threat intelligence against sophisticated financial crime networks.

Government agencies consolidating citizen data from disparate legacy systems into a modern sovereign cloud use PPRL to perform entity resolution. By linking records with privacy-preserving techniques, they can deduplicate citizen profiles for unified service delivery without decrypting the underlying personal identifiers during the matching process, maintaining a strict zero-trust posture even against the cloud provider's administrators.

Longitudinal social science studies often require linking survey responses to administrative data (tax records, education transcripts) held by different government departments. PPRL acts as a trusted intermediary. Researchers submit encoded study participant lists, and the data custodian performs the linkage on the encrypted fields. The researcher receives only the de-identified, linked dataset for analysis, never gaining access to the full administrative database.

Luxury goods manufacturers and pharmaceutical companies combat counterfeiting by linking serialized product tracking events across a fragmented supply chain. PPRL allows competitors and logistics partners to collaboratively query for duplicate or anomalous serial numbers appearing in different channels without revealing their proprietary sales volumes or customer destinations. This detects diversion and gray market activity while preserving trade secrets.

A cryptographic protocol enabling multiple parties to jointly compute a matching function over their private identifier sets. Each party contributes encrypted or secret-shared inputs, and the protocol reveals only the matched record IDs—no raw data is exposed to any participant. Common PPRL implementations use garbled circuits or secret sharing to compute similarity metrics like Jaccard index on encoded strings.

A probabilistic data structure that maps identifier attributes (e.g., names, dates of birth) into fixed-length bit vectors using multiple hash functions. PPRL systems compare these encrypted bit arrays using dice-coefficient or Hamming distance rather than raw strings. Key properties:

• One-way encoding: Cannot reverse-engineer original values
• Tunable false positive rate: Balances privacy against linkage accuracy
• Hardening techniques: Salting and random bit-flipping resist frequency attacks

Algorithms that convert names into phonetic hash codes to enable fuzzy matching across spelling variations and typographical errors—critical when linking records from different databases. Common schemes include:

• Soundex: Maps consonants to numeric codes, preserving the first letter
• Double Metaphone: Handles non-English origins and produces primary/secondary encodings
• Daitch-Mokotoff: Optimized for Eastern European and Jewish surnames These encodings are themselves privacy-sensitive and must be hashed or encrypted before transmission.

An encryption scheme permitting computation directly on ciphertext. In PPRL, a central linker can calculate similarity scores between encrypted record pairs without ever decrypting the underlying identifiers. The result remains encrypted and is only revealed to authorized parties. Partially homomorphic encryption (PHE) supports limited operations (addition or multiplication), while fully homomorphic encryption (FHE) enables arbitrary computation—though at significant computational cost, often making it impractical for large-scale linkage.

The preprocessing step that partitions records into blocks sharing common attributes (e.g., postal code, birth year) to avoid the quadratic complexity of comparing every record pair. Privacy-preserving blocking uses:

• Phonetic blocking keys: Encoded and hashed before exchange
• Locality-Sensitive Hashing (LSH): Maps similar Bloom filters to the same buckets with high probability
• Sorted neighborhood: Sliding window over sorted encoded values Effective blocking reduces comparisons by 99%+ while maintaining high recall.

A mathematical framework that injects calibrated noise into the linkage output to prevent inference about any single individual's presence in the datasets. Applied to PPRL through:

• Noisy matching thresholds: Adding Laplace noise to similarity scores
• Sparse vector technique: Releasing only statistically significant matches
• Privacy budget (ε): Quantifies total privacy loss—lower epsilon means stronger guarantees but reduced linkage accuracy This protects against membership inference attacks where an adversary deduces if a specific person exists in both databases.