Federated Record Linkage

The core mechanism that allows two parties to determine if their records match without revealing the underlying data. This is typically achieved through private set intersection (PSI) or homomorphic encryption protocols.

• Bloom filter encoding: Records are hashed into bit arrays, allowing approximate matching via set overlap metrics like Dice coefficient or Jaccard similarity
• Phonetic encoding: Strings are transformed into phonetic representations (Soundex, Double Metaphone) before encryption to handle typographical errors
• Reference value comparison: Instead of comparing raw values, parties compare encrypted tokens derived from agreed-upon reference tables

The comparison function operates entirely on encoded data, ensuring that even if the protocol is intercepted, no plaintext PII is exposed.

Comparing every record pair across databases is computationally infeasible. Blocking reduces the search space by grouping records into candidate blocks using quasi-identifiers before cryptographic comparison.

• Phonetic blocking: Uses Soundex or NYSIIS encodings of names to group similar-sounding records
• Locality-Sensitive Hashing (LSH): Hashes records so that similar inputs map to the same bucket with high probability
• Sorted neighborhood: Records are sorted by a blocking key, and a sliding window compares only adjacent records

Effective blocking dramatically reduces the number of expensive cryptographic comparisons while maintaining high recall of true matches.

Traditional record linkage relies on a central trusted party to perform matching. FRL eliminates this dependency through decentralized protocols where no single entity sees both datasets.

• Two-party protocol: Each data custodian encodes their records independently and exchanges only encrypted representations
• Three-party protocol with untrusted linker: A third party performs the matching on encrypted data but cannot decrypt the results
• Multi-party linkage: Extends to scenarios where records are distributed across many institutions, such as a network of hospitals linking patient cohorts

This architecture is critical for compliance with regulations like HIPAA and GDPR, where data cannot leave institutional boundaries.

The choice of encoding method directly impacts linkage quality. Records must be transformed into privacy-preserving representations that preserve similarity while resisting cryptanalysis.

• Bloom filter encoding: Maps q-gram sets of attribute values into bit vectors. The Dice coefficient between two Bloom filters approximates the true string similarity
• Tabulation min-hash: Generates compact signatures that preserve Jaccard similarity between sets of features
• Field-level hashing: Applies salted cryptographic hash functions (SHA-256) to individual fields, enabling exact matching only

Encoding must balance linkage accuracy against privacy guarantees. Bloom filters with appropriate parameters can resist frequency-based attacks while maintaining high match quality.

Once encrypted similarities are computed, FRL systems must classify record pairs as matches or non-matches without human review of plaintext data.

• Threshold-based classification: Pairs exceeding a predefined similarity threshold are declared matches
• Supervised classification: Trained on labeled match/non-match pairs from a subset of data where ground truth is available
• Hierarchical clustering: Groups records into clusters representing unique individuals, resolving transitive matches across multiple databases
• Active learning: Iteratively queries domain experts on high-uncertainty pairs to refine the classification model

The classification step must handle the inherent uncertainty of working with encoded data, where similarity metrics are approximations of true string distances.

FRL protocols must be hardened against adversaries who may attempt to re-identify individuals from encoded data or manipulate the linkage process.

• Frequency attacks: An adversary with knowledge of plaintext value distributions can attempt to map Bloom filter bit patterns back to original values. Countermeasures include salting, random bit flips, and differential privacy noise injection
• Collusion resistance: Protocols must remain secure even if a subset of participating parties collude
• Sybil attacks: Malicious entities may inject fabricated records to create false links. Rate limiting and institutional authentication mitigate this risk
• Output privacy: Even the final linkage results may leak information. Secure multiparty computation ensures only authorized parties learn the match outcomes

A probabilistic data structure used to encode personally identifiable information (PII) into a privacy-preserving bit vector. Bloom filters allow for approximate matching of records across databases by comparing bit positions without revealing the original plaintext values. This technique is foundational to many Privacy-Preserving Record Linkage (PPRL) protocols.

• Enables fast, memory-efficient set membership tests
• Configurable false positive rate to balance privacy and accuracy
• Resistant to dictionary attacks when combined with salted hashing

Algorithms like Soundex, Metaphone, and Double Metaphone that index names by their pronunciation rather than exact spelling. These are critical for deterministic record linkage in healthcare, where patient names often contain typographical errors, transliteration variations, or cultural naming conventions. Phonetic codes are often hashed before being used in federated contexts.

• Soundex: Maps names to a letter-digit code based on consonant sounds
• Double Metaphone: Handles non-English origins and produces primary/secondary encodings
• Reduces false negatives caused by simple spelling mistakes

The application of differential privacy (DP) guarantees to the record linkage process to protect against membership inference attacks. By injecting calibrated noise into the linkage results or the similarity scores, a curator can provably limit what an adversary can learn about any single individual's presence in the linked dataset.

• Provides a mathematical privacy budget (ε) for the linkage operation
• Trades off linkage accuracy for a formal privacy guarantee
• Essential for releasing aggregate statistics from linked data

A scalability technique that partitions large datasets into smaller blocks of candidate record pairs likely to match, drastically reducing the quadratic comparison space. In a federated setting, blocking keys (e.g., hashed tokens of zip code and gender) are exchanged to agree on which blocks to compare without revealing the full records.

• Prevents the need for all-pairs comparison (n x m complexity)
• Uses soundex, n-grams, or locality-sensitive hashing for block key generation
• Must balance block size to avoid missing true matches across block boundaries

An algorithmic technique that hashes similar input items into the same buckets with high probability. LSH is used in federated record linkage to efficiently cluster similar encrypted records together for comparison, enabling fuzzy matching on high-dimensional data like patient addresses or medical notes without pairwise comparison.

• Dramatically reduces computational overhead for fuzzy matching
• Works well with MinHash for Jaccard similarity on q-gram sets
• Preserves similarity relationships in the hashed space