Multi-Party Computation Linkage

The core cryptographic engine of MPC linkage. Each party splits its private identifiers into secret shares and distributes them. The linkage logic—often a Felligi-Sunter probabilistic model or a deterministic match key—is compiled into a Boolean or arithmetic circuit. Parties jointly evaluate this circuit on the shared fragments, learning only the final match result and nothing about non-matching records. This eliminates the single point of failure inherent in trusted third-party models.

MPC linkage supports flexible network topologies beyond simple pairwise connections:

• Star Topology: A central hub coordinates the computation, but only sees secret shares, not plaintext.
• Fully Connected Mesh: All parties communicate directly, increasing resilience but adding communication overhead.
• Hierarchical Topology: Sub-groups perform local linkage before passing encrypted intermediate results to a global resolver. This allows a consortium of hospitals, for example, to agree on a common governance model that matches their regulatory trust framework.

Comparing every record across all parties is computationally infeasible. MPC linkage integrates private blocking to reduce the quadratic search space without leaking similarity. Techniques include:

• Locality-Sensitive Hashing (LSH) on secret-shared Bloom filters to cluster likely matches.
• Private Set Intersection Cardinality (PSI-CA) to identify blocks with overlapping records before full comparison.
• Reference Value Encoding where parties map records to a common, pre-agreed reference table using secure protocols. This ensures the MPC circuit only evaluates high-probability candidate pairs, making consortium-wide linkage practical.

Standard two-party PPRL assumes semi-honest participants. MPC linkage for consortia must harden against malicious adversaries who may deviate from the protocol to learn others' data. Defenses include:

• Commitment Schemes: Parties cryptographically commit to their inputs before the protocol begins, preventing later manipulation.
• Zero-Knowledge Proofs: Each party proves in zero-knowledge that they correctly executed their step of the circuit without revealing their secret state.
• Fair Output Delivery: Protocols ensure that if any party learns the output, all honest parties do, preventing an abort-and-learn attack.

The final match results are encrypted under a threshold public key. Decryption requires a quorum of parties to contribute their key shares. This prevents any single entity from unilaterally viewing the linked records. The consortium can set the threshold—e.g., requiring 7 of 10 hospitals to agree before the matched patient cohort is revealed. This cryptographically enforces the data use agreement and is critical for compliance with regulations like GDPR's data minimization principle.

MPC linkage introduces significant overhead compared to cleartext matching. Key bottlenecks:

• Communication Complexity: The number of rounds scales with circuit depth. WAN latency between consortium members can dominate runtime.
• Circuit Depth: Complex fuzzy matching like Jaro-Winkler or edit distance requires deep circuits. Approximations like Dice coefficient on n-grams are often preferred for efficiency.
• Hardware Acceleration: Modern implementations leverage AES-NI instructions and GPU-accelerated oblivious transfer extensions to make consortium-scale linkage feasible for millions of records.

The foundational cryptographic primitive that underpins MPC linkage. A secret value—such as a record identifier or match key—is split into shares distributed among participating parties. No single share reveals anything about the original secret. Computation proceeds on the shares themselves, with the final result reconstructed only when a threshold of parties combines their shares. Common schemes include Shamir's Secret Sharing and additive secret sharing over finite fields.

A two-party protocol generalized to the multi-party setting for secure function evaluation. The linkage logic—such as edit distance or Jaccard similarity—is compiled into a boolean circuit. One party 'garbles' the circuit by encrypting each gate's truth table. Other parties evaluate the garbled circuit obliviously using their private inputs, learning only the final match decision. Yao's Garbled Circuits form the basis, with extensions like BMR for multi-party settings.

A critical building block where a sender transmits one of many pieces of information to a receiver, but remains oblivious to which piece was selected. In MPC-based record linkage, OT enables parties to privately look up and compare encoded identifiers without revealing which records they are querying. OT extension techniques dramatically reduce the number of expensive public-key operations required, making large-scale linkage feasible.

The security model defining how many parties an MPC protocol tolerates as corrupted or malicious. In honest-majority protocols, more than half the parties follow the protocol correctly—common in three-party linkage with one trusted auditor. Dishonest-majority protocols remain secure even if all but one party is corrupted, using techniques like SPDZ with message authentication codes (MACs) to detect cheating. The choice directly impacts computational overhead.

A specialized MPC protocol that allows multiple parties to compute the intersection of their private datasets without revealing elements unique to any party. In consortium linkage, PSI serves as a private blocking mechanism: parties first identify which encoded identifiers appear across all databases before performing more expensive pairwise comparisons. Circuit-based PSI and Diffie-Hellman-based PSI offer different efficiency-security tradeoffs.

A variant of secret sharing where values are split over a finite field (e.g., modulo a prime), enabling addition and multiplication directly on shares. In MPC linkage, similarity scores like weighted field agreement are computed as arithmetic circuits. Beaver triples—pre-computed correlated randomness—allow efficient multiplication of shared values without interaction. This approach underpins protocols like SPDZ and BGW used in production PPRL systems.