Secure multi-party computation

Secure multi-party computation (MPC) allows a set of parties, each holding a private input, to compute a public function of those inputs without revealing anything beyond the result. The canonical example is Yao's millionaire problem: two millionaires wish to determine who is richer without disclosing their actual wealth.¹ Formally, a protocol is secure if it simulates an ideal world where a trusted third party computes the function; this ensures that whatever an adversary can learn in the real protocol, they could also learn in the ideal world.

MPC guarantees two properties: privacy (inputs remain hidden) and correctness (the output is correct). Security is defined against two adversary models: semi-honest (passive, where parties follow the protocol but try to learn extra) and malicious (active, where parties may deviate arbitrarily).²

The two foundational approaches are garbled circuits (Yao's protocol) and secret sharing-based protocols. Garbled circuits, primarily for two parties, encrypt a Boolean circuit so that only the output is revealed. Secret sharing, such as Shamir's scheme, splits each input into shares distributed among parties; computations are performed on the shares, and the final result is reconstructed.³

Modern MPC protocols often combine these with homomorphic encryption and oblivious transfer to achieve efficiency. For example, the SPDZ protocol (pronounced "speedz") uses somewhat homomorphic encryption to preprocess multiplication triples, enabling fast online computation even against malicious adversaries.⁴ Other notable constructions include BMR (Beaver, Micali, Rogaway) for constant-round protocols and GMW (Goldreich, Micali, Wigderson) for general multi-party computation.

MPC has moved from theory to practice. In 2008, the first large-scale deployment was the Danish sugar beet auction, where multiple bidders' prices were aggregated without revealing individual bids.⁵ Since then, MPC has been used in privacy-preserving machine learning, secure voting, key management, and fraud detection across financial institutions.

Notable deployments include Google's Private Join and Compute for advertising measurement, and the Sharemind platform by Cybernetica, which has been used for statistical analysis of sensitive data. In healthcare, MPC enables collaborative research on genomic data without exposing patient records.⁶ The technology is also a key enabler for federated learning, where models are trained across decentralized data.

Beyond the mainstream, MPC has surprising niches. For instance, MPC for password breach checking allows users to check if their password has been compromised without revealing it to the service. The Honey Encryption concept, though distinct, is often discussed alongside MPC for its complementary approach to protecting low-entropy secrets.

An edge case is the fairness problem: in malicious settings, a corrupted party may abort after learning the output, leaving others in the dark. Achieving fairness is impossible in general without a trusted third party, but protocols like FairPlay and SPDZ provide partial solutions under certain assumptions.⁷ Another obscure fact: the first MPC protocol for secure integer comparison was proposed by Yao in 1982, but it was not until 2009 that an efficient implementation for large inputs was achieved using oblivious transfer extension.

Garbled circuits

A cryptographic technique that encrypts a Boolean circuit so that parties can evaluate it without learning intermediate values.

Secret sharing

A method to split a secret into shares distributed among parties, such that only authorized subsets can reconstruct it.

Semi-honest adversary

An adversary that follows the protocol but attempts to learn extra information from the transcript.

Malicious adversary

An adversary that may deviate arbitrarily from the protocol to compromise security.

Oblivious transfer

A primitive where a sender transfers one of many messages to a receiver without knowing which one was received.