Two-Party Computation Linkage

The cryptographic foundation enabling two-party computation linkage. Secure Multi-Party Computation (SMPC) allows mutually distrusting parties to jointly compute a function over their private inputs without revealing those inputs to each other.

• Garbled Circuits: A protocol where one party encrypts a Boolean circuit and the other evaluates it obliviously
• Secret Sharing: Additive splitting of data so no single share reveals the original value
• Oblivious Transfer: A primitive allowing a receiver to obtain one of several messages without the sender knowing which was selected

In the context of PPRL, SMPC enables two data custodians to compute the edit distance or Jaccard similarity between encoded records without ever exposing the underlying identifiers.

A cryptographic protocol that allows two parties to discover the intersection of their private sets without revealing any elements unique to either party.

• PSI-CA (Cardinality): A variant revealing only the size of the intersection, not the elements themselves
• Delegated PSI: Offloads computation to untrusted servers while maintaining input privacy
• Circuit-based PSI: Implements intersection logic within a generic SMPC framework

PSI serves as a critical building block for two-party computation linkage by enabling private blocking and reducing the candidate pair space before more expensive secure comparison operations.

A specialized SMPC protocol that computes the Levenshtein or Damerau-Levenshtein distance between two strings held by separate parties without revealing the strings themselves.

• Dynamic Programming over Garbled Circuits: Implements the edit distance matrix within a Boolean circuit evaluated obliviously
• Threshold Variants: Reveals only whether the distance falls below a predefined matching threshold
• Optimized Representations: Uses pathfinding algorithms to reduce circuit depth and communication overhead

This protocol is essential for fuzzy matching of encoded names and addresses in two-party computation linkage, enabling tolerance for typographical errors while maintaining cryptographic privacy guarantees.

A hardened encoding scheme that transforms personally identifiable information into irreversible, length-preserving tokens suitable for privacy-preserving record linkage.

• Salted Hash Composition: Multiple hash iterations with a secret salt prevent dictionary attacks
• Bloom Filter Foundation: Encodes n-grams of identifiers into a fixed-length bit array
• Length Preservation: Maintains consistent token size regardless of input length, simplifying secure comparison

CLKs are the most common encoding used in two-party computation linkage because they allow parties to pre-compute irreversible tokens locally before engaging in the expensive SMPC comparison phase.

The statistical framework for probabilistic record linkage that computes match weights based on agreement and disagreement patterns across record fields.

• M-Probability: The likelihood that a field agrees given the pair is a true match
• U-Probability: The likelihood that a field agrees by random chance
• Composite Weight: Sum of individual field weights used to classify pairs as match, non-match, or clerical review

In two-party computation linkage, the Felligi-Sunter model is implemented within an SMPC framework, allowing parties to jointly compute match probabilities over their encoded records without revealing individual field agreement patterns.

An algorithmic technique that hashes similar inputs into the same buckets with high probability, enabling efficient private blocking before secure comparison.

• MinHash: Estimates Jaccard similarity by comparing minimum hash values of sets
• SimHash: Produces similar fingerprints for similar documents using cosine similarity
• Band Partitioning: Divides hash signatures into bands to tune the precision-recall tradeoff

LSH dramatically reduces the quadratic complexity of two-party computation linkage by limiting expensive SMPC comparisons to record pairs that fall into the same hash bucket, all without revealing plaintext similarity.