Privacy-Preserving Record Linkage (PPRL)

The foundational PPRL technique that converts sensitive identifiers into a privacy-preserving bit array. Each attribute value is split into q-grams (substrings of length q), which are hashed multiple times into a fixed-length bit vector using a family of cryptographic hash functions.

• Hardening: Random bit flips or XOR-folding are applied to prevent frequency-based cryptanalysis attacks.
• Comparison: Encoded records are compared using set-based similarity metrics like the Dice coefficient or Jaccard index.
• Example: The name 'SMITH' is decomposed into bigrams (SM, MI, IT, TH), each hashed to set specific bits in a 1000-bit filter.

A noise-tolerant technique that encodes identifiers based on their pronunciation rather than exact spelling, mitigating typographical variation before cryptographic protection.

• Soundex & NYSIIS: Classic algorithms that map phonetically similar consonants to the same code.
• Double Metaphone: A more sophisticated algorithm that generates both a primary and secondary encoding for a name, accounting for alternative pronunciations and non-English origins.
• Workflow: A name is first converted to its phonetic hash, and this hash is then tokenized and encoded into a Bloom filter for secure comparison.

A cryptographic approach that allows computation directly on ciphertext, generating an encrypted result that, when decrypted, matches the result of operations performed on the plaintext.

• Partially Homomorphic Encryption (PHE): Supports only one type of operation (e.g., addition). The Paillier cryptosystem is commonly used to compute secure sums of matching weights.
• Fully Homomorphic Encryption (FHE): Supports arbitrary computation but is computationally prohibitive for large-scale linkage.
• Protocol: Two parties exchange encrypted record values, compute an encrypted similarity score, and only decrypt the final match result.

A protocol where multiple parties jointly compute a function over their private inputs without revealing those inputs to each other. In PPRL, this enables a privacy-preserving join.

• Garbled Circuits: A boolean circuit representing the matching logic is encrypted and evaluated by two parties in a constant-round protocol.
• Secret Sharing: Each party splits its data into random shares and distributes them. Computations are performed on the shares, and the final match result is reconstructed.
• Application: Three hospitals can identify common patients for a clinical trial without any hospital revealing its full patient list to the others.

A mathematical framework that injects calibrated statistical noise into the linkage process to provide a provable guarantee against the inference of any single individual's record.

• Epsilon (ε) Budget: A parameter controlling the privacy loss. A smaller epsilon (e.g., 0.1) provides stronger privacy by adding more noise.
• Laplace Mechanism: Noise drawn from a Laplace distribution is added to the similarity scores or match weights before a threshold is applied.
• Purpose: Protects against differencing attacks, where an adversary could deduce an individual's presence by comparing linkage outputs from two datasets differing by one record.

A hybrid technique that avoids direct comparison of encoded records by introducing a trusted third party or a secure hardware enclave that holds a set of reference values.

• Mechanism: Each data custodian encodes their records and sends them to the reference party, which performs the comparison and returns only the matched record identifiers.
• Trusted Execution Environment (TEE): A hardware-based isolated compute environment (e.g., Intel SGX) acts as the reference party, ensuring the comparison code and data are protected from the host operating system.
• Benefit: Allows the use of standard, high-accuracy string comparators without cryptographic modification.

The foundational statistical process of identifying and joining records across different datasets that correspond to the same real-world entity when a reliable unique identifier is absent. PPRL extends this concept by adding a cryptographic privacy layer.

• Deterministic vs. Probabilistic: Exact matching on a common key versus the Fellegi-Sunter model that calculates match weights based on attribute agreement patterns.
• Core Challenge: Resolving the identity of 'John Smith' in Database A and 'J. Smith' in Database B without a shared Social Security Number.

A core PPRL technique that converts sensitive identifiers like names and dates of birth into a privacy-preserving bit vector. This allows for approximate matching without storing or revealing the original plaintext data.

• Mechanism: Multiple cryptographic hash functions map attribute q-grams to a fixed-length binary array.
• Dice Coefficient: Similarity between two encoded records is calculated using set-based metrics on their Bloom filters, enabling fuzzy matching on encrypted data.

A computational efficiency technique critical for scaling PPRL to large databases. Blocking partitions datasets into mutually exclusive clusters using a cheap, privacy-preserving heuristic to avoid the impossible task of comparing every record pair.

• Phonetic Blocking: Uses Soundex or Double Metaphone encodings to group similar-sounding names before secure comparison.
• Locality-Sensitive Hashing (LSH): Hashes Bloom filters into buckets such that similar bit vectors collide with high probability, drastically reducing the comparison space.

The broader enterprise data management discipline of accurately matching and merging identity data across disparate systems to create a unified, 360-degree customer view. PPRL is the privacy-compliant engine that powers identity resolution in inter-organizational contexts.

• Master Data Management (MDM): The creation of a single 'golden record' for each customer or patient by consolidating data from multiple source systems.
• Cross-jurisdictional Use: Enables healthcare networks to link patient records for research without violating HIPAA or GDPR by sharing plaintext identifiers.

A complementary cryptographic technique often integrated with PPRL to provide a mathematical guarantee against inference attacks on the linkage results. It ensures that the output of a query or linkage does not reveal whether any single individual's data was included.

• Epsilon Parameter: A privacy budget that quantifies the information leakage risk; a lower epsilon (e.g., 0.1) provides stronger privacy.
• Noise Injection: Laplacian or Gaussian noise is added to the aggregate linkage statistics to mask individual contributions.

The string comparison technique that calculates the similarity between two text strings to identify non-exact duplicates, tolerating typographical errors, abbreviations, and formatting inconsistencies. In PPRL, this logic is applied to the encoded representations rather than the raw strings.

• Q-gram Tokenization: Breaking strings into small substrings of length 'q' to make comparisons robust to character-level noise.
• Edit Distance: Metrics like Levenshtein distance quantify the minimum operations needed to transform one string into another, informing match probability.