Overview

Secure multiparty computation

Protocols that let mutually distrusting parties compute a joint function of their private inputs while revealing nothing beyond the output, even when some parties are corrupted.

What it is

In secure multiparty computation (MPC), $n$ parties holding inputs $x_{1}, \dots, x_{n}$ run a protocol to compute $f (x_{1}, \dots, x_{n})$ . Security is defined by simulation. For every adversary corrupting at most $t$ parties in the real protocol, there is a simulator in an ideal world, where a trusted party computes $f$ , such that the adversary's view together with the honest parties' outputs is distributed identically (perfect security), statistically close (statistical), or computationally indistinguishable (computational). Two-party computation (2PC) is the case $n = 2$ . Yao posed the two-party problem (); and gave general protocols.

Core notions

Corruption threshold: the bound $t$ on corrupted parties. Honest majority means $t < n /2$ ; dishonest majority allows up to $t = n - 1$ .
Semi-honest versus malicious: a semi-honest (passive) adversary follows the protocol but reads the corrupted parties' state; a malicious (active) adversary deviates arbitrarily.
Static, adaptive, proactive: corruptions are fixed in advance, chosen during the run (), or move between epochs while shares are refreshed ().
Output guarantees: with security with abort, the adversary may learn the output and deny it to honest parties; identifiable abort also names a cheater; fairness gives everyone the output or no one; guaranteed output delivery (GOD) always gives honest parties the output. Fairness is impossible for general functions without an honest majority, although some functions admit it ().
Feasibility: with private channels, perfect security holds for $t < n /3$ malicious or $t < n /2$ semi-honest corruptions (); under computational assumptions, any $t < n$ is possible with abort ().
Network and composition: synchronous or asynchronous networks (); stand-alone or universally composable (UC) security ().
Preprocessing model: an input-independent offline phase produces correlated randomness, such as multiplication triples or oblivious-transfer (OT) correlations, which a fast online phase consumes ().
Representation: Boolean or arithmetic circuits, with values held as garbled labels or as additive, Shamir, or replicated secret shares.

Main approaches

Garbled circuits: one party encrypts the circuit gate by gate and another evaluates it, in a constant number of rounds (; multiparty: ). Per-gate cost fell with free XOR (), half gates (), and about 1.5 labels per AND gate ().
Secret-sharing evaluation: linear gates are local and each multiplication costs interaction. GMW-style Boolean sharing uses OT for each AND gate; Shamir sharing gives information-theoretic honest-majority protocols, generalized to multiplicative linear secret-sharing schemes ().
Authenticated preprocessing for dishonest majority: information-theoretic MACs on shares, with triples produced by somewhat homomorphic encryption () or by OT (, ).
Correlation generation: OT extension from a few base OTs () and pseudorandom correlation generators that expand short seeds locally (, , ).
Mixed protocols and frameworks: conversions between arithmetic, Boolean, and garbled representations (, , ) and general frameworks (). A 2019 survey compares eleven compilers by usability rather than speed and finds no standard benchmarks with which to measure them ().

Notation used in the comparison table

Parameters below occur in efficiency or security bounds. Each meaning is scoped to its stated regime. Measured quantities are named in words; protocol objects are defined where used. Source aliases do not equate different regimes.

Symbol	Meaning	Regime	Paper aliases
n	Number of participating parties.	General MPC.	writes n
t	Maximum number of corrupted parties in the security model.	MPC corruption threshold.	No paper spelling asserted.
κ	Computational security parameter.	Computational MPC; distinct from label length and statistical error.	writes λ
λ	Statistical security/error parameter.	Statistical MPC; the source specifies its error bound.	writes κ; writes κ
p	Prime field order.	Prime-field arithmetic MPC.	writes p
\|C\|	Circuit size in the source gate model.	Whole-circuit garbling.	No paper spelling asserted.
D	Circuit depth in the stated gate model.	Whole-circuit garbling.	No paper spelling asserted.
T	Upper bound on adversary random-oracle queries.	LS26 query-bounded garbling.	No paper spelling asserted.
W_I	Number of circuit input wires.	LS26 input encoding.	No paper spelling asserted.
B	Number of candidate branches.	Stacked garbling.	writes B
I	Shared input length of one branch, in bits.	Stacked garbling.	writes I
r	Number of protocol rounds.	Fairness and coin-flipping bounds.	No paper spelling asserted.

This topic covers general-purpose 2PC and $n$ -party MPC over Boolean, arithmetic, or mixed circuits, against passive or active adversaries with honest or dishonest majority. Threshold signatures, private set intersection, and private machine learning appear only when they change a general mechanism; MPC-in-the-head belongs to proof systems.