In 1982, Andrew Chi-Chih Yao posed a deceptively simple problem: two millionaires wish to determine who is richer without revealing their actual wealth to each other or to any trusted third party. This inquiry birthed Secure Multi-Party Computation (MPC): allowing a set of mutually distrustful participants ({P_1, dots, P_n}) holding private inputs ((x_1, dots, x_n)) to collaboratively compute any public function (y = f(x_1, dots, x_n)) such that no party learns anything beyond their own input and the final output.
1. The Two-Party Engine: Yao’s Garbled Circuits
For two parties (Alice and Bob), Yao introduced Garbled Circuits, transforming arbitrary Boolean circuits into encrypted look-up tables:
- Garbling (Alice): For every wire (w) in the circuit, Alice randomly assigns two 128-bit cryptographic keys representing Boolean values: (W_w^0) (for 0) and (W_w^1) (for 1). For each gate (e.g., AND gate with input wires (u, v) and output wire (w)), Alice encrypts the output wire label under the two corresponding input wire labels:
[
ext{Entry}_{a, b} = ext{Enc}_{W_u^a, W_v^b}(W_w^{a wedge b}) quad ext{for } a, b in {0, 1}
]
She randomly permutes (garbles) the four entries so row positions reveal no truth values. - Input Wire Transmission: For her own input bit (x_A), Alice directly sends Bob the single corresponding wire key (W_{ ext{in1}}^{x_A}). For Bob’s input bit (x_B), Alice and Bob execute 1-out-of-2 Oblivious Transfer (OT): Bob receives his wire key (W_{ ext{in2}}^{x_B}) without revealing his bit (x_B) to Alice, and without learning the alternate key.
- Evaluation (Bob): Possessing exactly one key per input wire, Bob decrypts exactly one entry per garbled gate table sequentially through the circuit. Finally, Bob maps the final output wire label to the public result bit.
Yao’s garbled circuits achieve optimal round complexity: a single round of communication with computational security against semi-honest (honest-but-curious) adversaries.
2. The BGW Protocol (Ben-Or, Goldwasser, Wigderson)
While Yao provides computational security for two parties, what if we demand information-theoretic (unconditional) security for (n) parties? In 1988, Ben-Or, Goldwasser, and Wigderson (BGW), and independently Chaum, Crépeau, and Damgård (CCD), demonstrated that any function can be computed with perfect security using Shamir secret sharing:
- Linear Gates (Addition): Every party holds a share of input (x) and (y) on polynomials of degree (t): ([x]_i = f_x(i)) and ([y]_i = f_y(i)). Addition is strictly local with zero communication:
[
[x + y]_i = [x]_i + [y]_i
] - Non-Linear Gates (Multiplication): Direct multiplication of shares ([x]_i cdot [y]_i) produces points on a product polynomial (H(X) = f_x(X) f_y(X)) of degree (2t). If (n ge 2t + 1), the parties execute a degree-reduction step via Beaver multiplication triples or secret-shared re-randomization.
The BGW Theorem proves that information-theoretic MPC is achievable if and only if fewer than (n/2) parties are passively corrupt, or fewer than (n/3) parties are actively malicious (Byzantine).
3. Modern MPC: Beaver Triples and Threshold Signing
In modern industrial MPC, computational bottlenecks are shifted to an offline preprocessing phase using Beaver Triples: pre-generated random triplets ((a, b, c)) satisfying (c = a cdot b). In the online phase, multiplying secret values ([x]) and ([y]) requires merely broadcasting two blinded values (psilon = x – a) and (delta = y – b), reducing online latency to sub-millisecond roundtrips. MPC powers modern digital asset self-custody (Fireblocks, Coinbase), threshold validator signing, and multi-hospital cancer research collaborations.
