Privacy-Preserving Record Linkage (PPRL)

Sensitive attributes like names and dates are transformed into irreversible, length-preserving tokens using hardened data structures. This prevents the exposure of raw identifiers during the linkage process.

• Bloom Filter Encoding: Maps bigrams of identifiers into a bit-array using multiple hash functions, enabling approximate matching via set overlap.
• Cryptographic Longterm Key (CLK): A salted and iteratively hashed variant of Bloom filters that resists frequency-based cryptanalysis.
• Phonetic Encoding: Indexes words by pronunciation (e.g., Soundex) to match homophones without revealing the original spelling.

To avoid the quadratic complexity of comparing every record pair, PPRL partitions datasets into blocks using privacy-preserving techniques that do not leak plaintext similarity.

• Locality-Sensitive Hashing (LSH): Hashes similar encoded records into the same bucket with high probability, drastically reducing candidate pairs.
• Sorted Neighborhood Method: Sorts records by an encoded key and slides a fixed window to compare only nearby records.
• Private Set Intersection Cardinality (PSI-CA): Allows parties to learn only the size of the overlapping block without revealing the elements themselves.

Instead of exact deterministic rules, PPRL uses statistical models to calculate the likelihood that two encoded records refer to the same entity, accounting for data errors and missing values.

• Felligi-Sunter Model: The foundational framework that computes match weights based on the agreement and disagreement patterns of individual fields.
• Edit Distance Thresholds: Fuzzy matching parameters like Levenshtein or Jaro-Winkler distance that define the maximum allowable string transformation cost for equivalence.
• Match Score Thresholding: Composite similarity scores are used to automatically classify pairs as matches, non-matches, or candidates for clerical review.

PPRL protocols allow multiple data custodians to jointly compute matching records without a trusted third party, ensuring no single entity sees the full dataset.

• Two-Party Computation: Two custodians use secure multi-party computation to identify intersections without revealing non-matching records.
• Multi-Party Computation: Extends secure linkage to consortia of three or more organizations, enabling collaborative entity resolution.
• Secure Edit Distance: A specialized protocol that computes the string edit distance between two private inputs without exposing the underlying strings.

The final output is a set of resolved entities, often represented as a golden record, with rigorous quality metrics to validate the linkage.

• Transitive Closure: A graph-based technique that merges all connected record pairs into a single entity cluster, ensuring consistency.
• Golden Record Creation: The best-curated version of a master data entity created by resolving conflicting attributes through survivorship rules.
• Linkage Quality Assessment: Evaluated using precision, recall, and F-measure against ground truth to measure false match rates and false non-match rates.

A probabilistic data structure that encodes sensitive identifiers into a bit-array using multiple hash functions. Hardened variants incorporate secret salts to resist frequency-based cryptanalysis. Key properties:

• Enables approximate matching without plaintext comparison
• Length-preserving output prevents length-based inference
• Configurable false positive rate via bit-array size and hash count

The foundational statistical framework for probabilistic record linkage. Computes match weights based on agreement/disagreement patterns across fields:

• M-probability: likelihood of agreement given a true match
• U-probability: likelihood of agreement given a true non-match
• Composite weight = log₂(M/U) for each field
• Summed weights determine match, non-match, or clerical review classification

A cryptographic preprocessing step that partitions encoded datasets to reduce the quadratic comparison complexity from O(n²) to near-linear. Techniques include:

• Locality-Sensitive Hashing (LSH): hashes similar items into same buckets
• Reference Value Encoding: clusters records by similarity to reference patterns
• TF-IDF Blocking: uses discriminative token weighting for text-heavy linkage
• Critical for scaling PPRL to millions of records without revealing plaintext similarity

A hardened encoding scheme derived from Bloom filters that generates irreversible, length-preserving tokens from personal identifiers. CLK construction:

• Multiple hash functions map q-gram subsets to a bit vector
• A secret cryptographic salt prevents rainbow table attacks
• Record-level random bit flipping adds controlled noise
• Enables secure linkage without trusted third parties in multi-party protocols

The systematic evaluation of record linkage output against ground-truth data. Core metrics:

• Precision: true matches / all predicted matches
• Recall: true matches / all actual matches
• F-measure: harmonic mean of precision and recall
• False Match Rate: incorrectly linked pairs among true non-matches
• False Non-Match Rate: missed true matches among all true matches
• Requires curated golden record datasets for reliable benchmarking

A secure multi-party computation protocol enabling two parties to compute the string edit distance between their private inputs without revealing the underlying strings. Applications in PPRL:

• Fuzzy matching on encrypted identifiers
• Levenshtein or Damerau-Levenshtein distance computation under encryption
• Garbled circuit implementations for efficiency
• Enables privacy-preserving typo-tolerant matching across organizational boundaries