What Is Multi-party Computation?

Multi-party computation (MPC) is a cryptographic framework that enables two or more parties to jointly evaluate a function over their combined private inputs without any party revealing its input to the others. At the conclusion of the protocol, each participant learns only the function output, not the private data that other parties contributed. The field emerged from Andrew Yao's work in the early 1980s on the "millionaires' problem," which asked whether two parties could determine who is wealthier without disclosing their individual wealth. The discipline draws on number theory, complexity theory, and probability, and it is now a central topic within applied cryptography.

The core security requirement is that a protocol is considered secure if what any party learns during execution is no more than what it could compute from its own input and the final output alone. This definition holds even when some parties behave maliciously, attempting to deviate from the protocol or to extract extra information from the messages they receive. Formal security models distinguish between semi-honest adversaries, who follow the protocol steps but try to infer extra information, and malicious adversaries, who may send arbitrary messages. NIST's Multi-Party Threshold Cryptography project reflects the practical importance of MPC by soliciting standardized threshold schemes for cryptographic primitives used in federal systems.

Secret Sharing

Secret sharing is a foundational building block for MPC protocols. In Shamir's secret sharing, introduced in 1979, a secret value is encoded as the constant term of a randomly chosen polynomial of degree t, and shares are distributed as evaluations of that polynomial at distinct points. Any t+1 shares suffice to reconstruct the secret via polynomial interpolation, while any t or fewer shares reveal nothing. MPC protocols based on secret sharing distribute computation over shares, so intermediate values during computation are also held in shared form and the underlying data is never concentrated at any single node. This architecture provides natural fault tolerance: up to a threshold of corrupted or failed parties can be tolerated without compromising security or correctness. A pragmatic introduction to secure multi-party computation by David Evans provides a thorough treatment of how secret-sharing-based protocols handle arithmetic and boolean circuits.

Garbled Circuits

Garbled circuits are a two-party computation technique, also introduced by Yao, that encrypts the truth tables of a boolean circuit so that one party can evaluate the circuit on its input while learning only the output. The circuit constructor encodes each wire with two random labels representing the bit values 0 and 1, then encrypts each gate's output label using the pair of input labels. The evaluator, holding one label per input wire obtained via oblivious transfer, can decrypt exactly one output label per gate without learning the other labels or the underlying bit values. Modern garbled circuit implementations apply techniques such as free-XOR optimization and half-gates construction to reduce the per-gate communication cost. Garbled circuits remain the method of choice for low-latency two-party computation because they require only a constant number of communication rounds regardless of circuit depth.

Practical Protocols and Security Models

Beyond the two foundational approaches, a range of specialized protocols has been developed for concrete deployment scenarios. Homomorphic encryption supports MPC by allowing computations directly on ciphertext, though at higher computational cost than secret sharing. Oblivious RAM protocols extend MPC to memory-access patterns. The threshold cryptography work supported by NIST's privacy-enhancing cryptography program targets MPC protocols for key management, digital signatures, and random beacon generation in institutional settings, emphasizing standardization of security parameters and adversarial models.

Applications

Multi-party computation has applications in a wide range of disciplines, including:

• Privacy-preserving machine learning on distributed datasets
• Secure collaborative analysis of financial and health records
• Threshold key management for digital asset custody
• Federated identity verification without centralizing personal data
• Secure auctions and voting protocols in electronic governance
• Private set intersection for fraud detection across organizations