Multi-Party Computation (MPC)

The foundational building block of most MPC protocols. A private input value is split into mathematically random shares distributed among computing parties. No single share reveals anything about the original input; the secret can only be reconstructed when a threshold of shares is combined.

• Additive sharing: A value x is split into n random shares that sum to x modulo a prime field.
• Shamir's Secret Sharing: Uses polynomial interpolation; any t+1 out of n shares can reconstruct the secret, while t or fewer reveal nothing.
• Shares enable computation because parties can perform local operations on their fragments that, when recombined, yield the correct result of the joint function.

A two-party MPC protocol where one party, the garbler, encrypts a boolean circuit representing the target function. The other party, the evaluator, obliviously evaluates the encrypted circuit using their own private inputs without learning the circuit's internal wires.

• The garbler assigns two random cryptographic labels to each wire (representing 0 and 1).
• Each logic gate is replaced with an encrypted truth table that only reveals the correct output label given valid input labels.
• Oblivious Transfer (OT) is used to securely deliver the evaluator's input labels without the garbler learning which labels were selected.
• Highly efficient for functions expressible as shallow boolean circuits; often used in Hybrid MPC-HE Protocols for non-linear operations.

MPC protocols are categorized by their adversarial model, which defines how many corrupted parties the system can tolerate while maintaining security guarantees.

• Honest-Majority: Assumes a strict majority of computing parties follow the protocol correctly. Enables extremely fast, information-theoretically secure protocols using secret sharing. Typically tolerates up to n/2 passive corruptions or n/3 active corruptions.
• Dishonest-Majority: Assumes an adversary may corrupt all but one party. Requires computationally secure primitives like garbled circuits or Threshold FHE. Significantly higher computational overhead but provides security under the strongest threat models.
• The choice directly impacts latency, throughput, and the trust assumptions required of the deployment environment.

MPC provides two critical security properties that distinguish it from other privacy technologies. Input privacy ensures that no party learns anything about another party's private data beyond what is inferable from the designated function output.

• Guaranteed Output Delivery (GOD): The strongest correctness guarantee. All honest parties are assured of receiving the correct computation result, regardless of adversarial behavior by corrupted parties.
• Fairness: A weaker property ensuring that if any party learns the output, all parties learn it. Prevents an adversary from aborting the protocol after receiving the result while denying it to honest participants.
• Abort security: The weakest model; a corrupted party can force the protocol to halt without output, but cannot violate input privacy or cause incorrect results to be accepted.

A specialized MPC protocol allowing two parties to compute the intersection of their private datasets without revealing any elements outside that intersection. In the AI context, PSI is used for privacy-preserving feature alignment in vertical federated learning, where organizations hold different attributes for overlapping users. It enables secure entity resolution without exposing customer lists to competitors.

A fundamental cryptographic building block where a sender transmits one of potentially many pieces of information to a receiver, but remains oblivious to which piece was selected. OT is the atomic primitive underlying most efficient MPC protocols, including Garbled Circuits. Modern OT extension techniques dramatically reduce the computational cost, making it practical for high-volume secure computation in AI pipelines.

The foundational mechanism for MPC where a secret value is split into random shares distributed among parties. Individually, shares reveal nothing about the original value; only a sufficient threshold of shares can reconstruct it. Common schemes include:

• Additive sharing: splits a value into random components that sum to the original
• Shamir's Secret Sharing: uses polynomial interpolation for threshold-based reconstruction This enables linear operations to be performed locally on shares without communication.

A two-party MPC protocol where a function is represented as a boolean circuit with encrypted truth tables. The garbler encrypts the circuit; the evaluator obliviously computes it using OT to retrieve input keys. Garbled circuits excel at evaluating non-linear functions with constant-round communication, making them ideal for the activation function evaluation in Hybrid MPC-HE inference architectures.