Secure Multiparty Computation

Secure multiparty computation (MPC) lets mutually distrustful parties jointly compute a function of their private inputs while revealing nothing beyond the agreed output.

Definition

Secure multiparty computation is a protocol enabling a set of parties, each holding a private input, to compute an agreed function such that every party learns the correct output and nothing else about the others' inputs.

Scope

This topic covers protocols for secure computation: the ideal/real simulation security definition, Yao's garbled circuits for two parties, secret-sharing-based protocols (GMW, BGW) for many parties, the distinction between semi-honest and malicious security, and threshold cryptography. It addresses practical applications such as private set intersection and secure aggregation. It excludes the zero-knowledge proofs often used as a sub-protocol and the fully homomorphic encryption that offers an alternative route to computing on encrypted data.

Core questions

• How can parties compute on combined data without any party seeing the others' inputs?
• What does the ideal/real simulation paradigm require of a secure protocol?
• How do garbled circuits enable secure two-party computation?
• How do secret-sharing-based protocols scale to many parties and tolerate corruptions?
• What is the difference between semi-honest and malicious security guarantees?

Key concepts

• private inputs and joint output
• ideal/real simulation
• garbled circuits
• oblivious transfer
• secret sharing
• semi-honest vs malicious adversary
• threshold cryptography
• private set intersection
• honest-majority vs dishonest-majority

Key theories

Ideal/real simulation security

An MPC protocol is secure if whatever an adversary can achieve in the real protocol it could also achieve in an ideal world where a trusted party computes the function — guaranteeing privacy and correctness against the modeled corruptions.

Garbled circuits and secret sharing

Yao's garbled circuits let two parties evaluate any Boolean circuit by one party encrypting truth tables and the other obliviously decrypting; secret-sharing schemes split inputs among parties so that subsets jointly compute gates without reconstructing the secrets.

Mechanisms

In Yao's two-party protocol, one party garbles a Boolean circuit by encrypting each gate's truth table and the other evaluates it using keys obtained via oblivious transfer, learning only the output. In secret-sharing approaches (GMW, BGW, SPDZ), each input is split into shares distributed among parties; addition gates are computed locally on shares and multiplication gates use interaction, after which the output shares are reconstructed. Malicious security adds zero-knowledge proofs or authenticated shares to detect cheating.

Clinical relevance

MPC is moving from theory to deployment for privacy-preserving collaboration: institutions compute aggregate statistics over combined datasets without pooling raw data (the Boston gender wage-gap study), companies run private set intersection for contact discovery and ad measurement, threshold signatures protect cryptocurrency custody and certificate-authority keys, and secure aggregation supports privacy-preserving machine learning.

Evidence & guidelines

MPC is supported by mature open frameworks (e.g., MP-SPDZ) and increasingly by standards efforts in threshold cryptography (NIST's Multi-Party Threshold Cryptography project). Security guarantees depend critically on the assumed corruption model (semi-honest vs malicious) and the corruption threshold (honest majority vs dishonest majority), which must match the deployment's trust assumptions.

History

Andrew Yao introduced secure two-party computation and the garbled-circuit idea in 1982-1986 (the millionaires' problem). Goldreich, Micali, and Wigderson (1987) extended secure computation to any number of parties, and the BGW and CCD protocols (1988) gave information-theoretic security with an honest majority. Decades of efficiency improvements (oblivious-transfer extension, SPDZ) made MPC practical enough for real deployments in the 2010s.

Key figures

• Andrew Yao
• Oded Goldreich
• Silvio Micali
• Avi Wigderson
• Adi Shamir

Seminal works

• yao1982
• goldreich2004
• katz2020

Frequently asked questions

How is MPC different from homomorphic encryption?

Both compute on private data, but homomorphic encryption lets a single party compute on ciphertexts it cannot read, whereas MPC distributes the computation among several parties who interact, with no single party able to see the inputs. They are sometimes combined.

What does 'semi-honest' versus 'malicious' security mean?

Semi-honest (honest-but-curious) security assumes parties follow the protocol but try to learn extra information from what they see. Malicious security additionally protects against parties that deviate arbitrarily from the protocol, which is stronger but more costly.