Secure Multi-Party Computation

Core Idea

Secure multi-party computation (MPC) allows n parties, each holding private input x_i, to jointly compute a function f(x_1,...,x_n) such that each party learns only the output and nothing about others' inputs beyond what the output implies. Security is defined by the ideal/real paradigm: the real protocol must be indistinguishable from an ideal world where a trusted third party collects inputs and distributes outputs. MPC is feasible for any function: with honest majority, information-theoretic security is achievable (BGW protocol); without honest majority, computational security is achievable using oblivious transfer. Applications include private auctions, joint statistical analysis, and threshold key management.

Explainer

Secure multi-party computation (MPC) addresses a fundamental question: can multiple parties compute a joint function of their private inputs without trusting anyone — not each other, not a central server, not any individual participant? The answer, remarkably, is yes. MPC protocols enable n parties, each holding a secret input, to compute any agreed-upon function and learn only the output, with the guarantee that the protocol reveals nothing about any party's input beyond what the output logically implies.

Security is defined via the ideal/real paradigm. In the ideal world, a perfectly trusted third party collects all inputs, computes the function, and returns the output — this is maximally secure because the only information anyone learns is the output. In the real world, parties run a cryptographic protocol with no trusted party. The protocol is secure if no efficient adversary can distinguish the real-world execution from the ideal world. This definition automatically captures every conceivable security property (privacy, correctness, input independence, fairness) without enumerating attacks — if the real and ideal worlds are indistinguishable, any property that holds in the ideal world also holds in the real one.

Two foundational results establish MPC's feasibility. Yao's garbled circuits (1986) solve the two-party case: one party converts the function into a Boolean circuit and "garbles" it — replacing wire values with random labels and encrypting truth tables. The other party evaluates the garbled circuit using their input labels (obtained via oblivious transfer) without learning intermediate wire values. The BGW protocol (1988) handles the multi-party case with honest majority using Shamir secret sharing: each party distributes shares of their input, and the function is computed on shares. Addition is free (add shares locally); multiplication requires one round of communication using the honest majority to reconstruct intermediate products securely. With honest majority, BGW achieves information-theoretic security — no computational assumptions needed.

MPC has moved from theory to practice over the past decade. Deployment scenarios include private auctions (bidders submit sealed bids; the protocol determines the winner without revealing losing bids), medical research (hospitals compute statistics across patient databases without sharing records), financial regulation (banks demonstrate compliance without revealing proprietary trading data), and threshold key management (a signing key is split among n parties, and t of them must cooperate to sign). Protocol efficiency has improved dramatically: modern MPC systems process millions of gates per second using optimized garbled circuits, oblivious transfer extensions, and preprocessing models that move expensive computation offline. While still orders of magnitude slower than direct computation, MPC is now fast enough for many practical applications.