Private Record Linkage

Reduces the quadratic comparison space by grouping candidate record pairs using blocking keys without revealing plaintext identifiers.

• Uses Bloom filter encoding of q-grams or phonetic codes to represent blocking keys as encrypted sets
• Enables private set intersection (PSI) on blocking key sets to identify candidate blocks across parties
• Prevents linkage attacks by ensuring blocking keys are never exchanged in plaintext
• Common techniques include phonetic blocking (Soundex, Double Metaphone) and token-based blocking on encrypted n-grams
• Dramatically reduces computational overhead from O(n²) to near-linear complexity while maintaining privacy guarantees

Encodes record attributes into probabilistic data structures that enable private similarity computation without revealing the underlying values.

• Each record's identifying fields (name, address, DOB) are tokenized into q-grams and hashed into a Bloom filter
• The Dice coefficient or Jaccard similarity between two Bloom filters approximates string similarity of the original plaintext
• False positives are controllable through filter parameters (length, number of hash functions)
• Hardening techniques like balancing, XOR-folding, and salting defend against frequency-based cryptanalysis
• Enables approximate matching for fuzzy record linkage while maintaining cryptographic privacy

Applies decision models to the computed similarity scores to classify record pairs as matches, non-matches, or potential matches without human access to raw data.

• Uses deterministic thresholds where pairs exceeding a predefined similarity score are automatically linked
• Probabilistic classification employs Fellegi-Sunter models to estimate match probability based on agreement patterns across multiple fields
• Clerical review can be invoked for pairs falling in an indeterminate range, but reviewers only see masked or encrypted representations
• Thresholds are tuned using ground-truth data or synthetic datasets that mirror the statistical properties of the private data
• Supports transitive closure to resolve multi-database linkage chains without re-identifying intermediate records

Enables the secure exchange of persistent pseudonymous identifiers for matched records so that linked data can be integrated without revealing original identifiers.

• After a match is confirmed, parties exchange cryptographic match keys derived via a one-way function rather than plaintext record IDs
• Uses keyed hash functions (HMAC) or oblivious pseudorandom functions (OPRF) to generate consistent, non-invertible identifiers
• Match keys are database-specific, preventing cross-database correlation by unauthorized parties
• Supports incremental linkage where new records can be matched against previously linked datasets using the same key derivation
• Ensures compliance with data minimization principles under GDPR and HIPAA by limiting exchanged information to what is strictly necessary

Incorporates defenses against cryptanalytic attacks that attempt to re-identify records from the encoded representations exchanged during linkage.

• Frequency-based attacks exploit non-uniform distribution of Bloom filter bit positions; countered by balancing (setting additional random bits to achieve uniform bit density)
• Pattern mining attacks identify co-occurring q-gram patterns; mitigated by salting with record-specific secrets and XOR-folding to collapse the filter space
• Dictionary attacks attempt to brute-force encoded values by hashing common names; defended by keyed hashing where the hash key is kept secret between parties
• Composability analysis ensures that multiple linkage runs do not leak incremental information beyond the intersection result
• Formal security proofs in the semi-honest and malicious adversary models provide guarantees about what information is provably protected

Extends private record linkage beyond two parties to enable collaborative entity resolution across multiple organizations without a trusted central party.

• Uses multi-party PSI protocols to identify records present in all or a threshold number of databases
• Secure multi-party computation (MPC) enables joint similarity computation across three or more parties without revealing individual contributions
• Supports star topology (central coordinator with pairwise links) and peer-to-peer topology (fully distributed) architectures
• Deduplication across multiple sources ensures that the final linked dataset contains each real-world entity only once
• Critical for public health surveillance, anti-money laundering, and fraud detection consortia where multiple institutions must collaborate without exposing their full customer bases

Pharmaceutical companies use PRL to identify overlapping patients across hospital networks and research databases without exposing the full patient rosters of either institution.

• Links patients across disparate Electronic Health Record (EHR) systems
• Enables recruitment for rare disease trials by finding patients matching complex criteria
• Maintains HIPAA compliance by never revealing non-matching patient identities
• Reduces cohort identification time from months to days

Financial intelligence units use PRL to link suspicious entities across international transaction databases without violating data sovereignty laws.

• Matches sanctioned individuals across disparate banking ledgers
• Identifies money laundering rings by linking shell company records
• Preserves investigative confidentiality by hiding non-suspect records
• Enables collaborative analytics between competing financial institutions

Government health agencies use PRL to merge census data with hospital records for epidemiological studies without exposing citizen identities.

• Links birth registries with immunization databases to measure vaccination coverage
• Connects cancer registries across state lines without centralizing sensitive data
• Enables population health analytics while maintaining strict citizen privacy guarantees
• Supports evidence-based health policy without compromising individual confidentiality

Enterprises migrating to cloud infrastructure use PRL to identify duplicate customer records across legacy systems without exposing the full dataset to the migration tool.

• Matches customer profiles across acquired company databases during M&A integration
• Identifies redundant records in multi-tenant cloud environments
• Preserves data compartmentalization between business units
• Reduces storage costs by eliminating duplicates before migration

Universities use PRL to link longitudinal study participants across institutions without revealing the full cohort to collaborators.

• Matches participants in multi-site public health studies
• Enables joint research on sensitive topics while protecting subject anonymity
• Preserves institutional review board (IRB) compliance across jurisdictions
• Facilitates open science without compromising participant trust

Claims databases across competing insurers are linked via PRL to identify organized fraud rings filing coordinated claims without exposing legitimate policyholder data.

• Matches claimant identities across insurers without revealing full customer bases
• Detects patterns of staged accidents and inflated medical claims
• Maintains competitive data confidentiality between participating carriers
• Reduces false positive fraud flags by correlating cross-insurer signals

A space-efficient probabilistic data structure used to test whether an element is a member of a set. In PPRL, Bloom filters encode sensitive identifiers (e.g., names, dates of birth) into bit arrays, allowing approximate matching via set similarity metrics like Dice coefficient or Jaccard index.

• No false negatives: If the filter says an element is absent, it definitely is.
• Controllable false positives: Tuning the filter size and number of hash functions balances privacy against linkage accuracy.
• Privacy limitation: Bloom filters are vulnerable to frequency-based cryptanalysis attacks, necessitating additional hardening techniques like XOR-folding or adding random noise.

A hashing scheme that resolves collisions by relocating existing keys using two or more hash functions. In PSI and PPRL protocols, Cuckoo hashing is used to optimize the placement of one party's set elements into bins, drastically reducing the communication and computational overhead of the subsequent secure comparison.

• How it works: Each element is assigned to one of two possible bins. If a bin is full, the occupying element is evicted and moved to its alternate location, potentially triggering a cascade.
• Stash: A small overflow area for elements that cannot be placed without cycles, typically sized for a negligible fraction of the input.
• Benefit: Ensures that each bin contains at most one element from the sender's set, allowing the receiver to perform only a single comparison per bin.

A variant of Private Set Intersection that identifies approximate matches between elements rather than requiring exact equality. This is essential for record linkage because real-world identifiers often contain typographical errors, phonetic variations, or formatting inconsistencies.

• Distance metrics: Uses edit distance (Levenshtein), Jaccard similarity on q-gram sets, or phonetic encodings (Soundex, Double Metaphone) to quantify closeness.
• Threshold tuning: Parties agree on a similarity threshold above which records are considered a match, balancing precision and recall.
• Challenge: Securely computing approximate matching is significantly more complex than exact matching, often requiring garbled circuits or homomorphic encryption to evaluate the distance function privately.

A cryptographic security model that guarantees protocol correctness and privacy even when an adversary arbitrarily deviates from the protocol specification. For PPRL in adversarial environments, malicious security prevents a corrupt party from learning extra information by sending malformed messages or aborting early.

• Real-world necessity: Essential when linking records between mutually distrustful organizations, such as competing financial institutions or intelligence agencies.
• Cost: Maliciously secure protocols are typically 2-10x slower than their semi-honest counterparts due to additional consistency checks and zero-knowledge proofs.
• Techniques: Cut-and-choose, authenticated garbling, and SPDZ-style MACs are common approaches to upgrading semi-honest protocols to malicious security.