The Trusted Party Nobody Has to Be: Secure Multiparty Computation and Threshold Cryptography, Where No One Holds the Secret

1. Compute on It, but Nobody Gets to See It#

Two hospitals each hold half the patients in a rare-disease study, and one shared statistic could save lives. Neither is allowed to see the other's records. The obvious fix, "hand both datasets to a trusted broker," just moves every secret into a single database that can be hacked, subpoenaed, or bribed. Down the street, a custodian must sign a billion-dollar transfer, and any one server that holds the signing key is one breach away from catastrophe. In each case the answer everyone reaches for -- a trusted party in the middle -- is precisely the party nobody can afford to trust.

This article is about the forty-five-year project to build that party out of pure protocol, so that no one ever has to be it. That is the one idea the whole piece defends: mutually distrusting parties can jointly compute a function over private inputs while learning only the output, and the special case where the function is "sign" or "decrypt" splits a key so that no single party -- or box -- ever holds it ^[1].

One refrain recurs in every section: each technique is a different way to simulate an incorruptible trusted party -- one who takes all private inputs, computes the agreed function, and returns only the result, without anyone ever getting to play that party.

Three sharp lines keep the primitives from blurring together, because this is Part 3 of a series and each part hides data a different way.

The invariant that ties them is blunt: no party ever sees a value in the clear that it is not entitled to see. Everything below is the machinery that enforces it, and the honesty about what the machinery still cannot do.

The trusted third party is not the cure. It is the disease. Its database is the breach surface, and the same box that can compute the answer can be hacked, subpoenaed, or bribed. MPC's move is not to make the trusted party safer -- it is to remove it entirely, and simulate its behavior with a protocol that gives the same output and leaks nothing more.

Every technique in this article is a different way to simulate the trusted party nobody has to be.

Before we can build a party out of protocol, though, we need to say precisely what "secure" even means. Otherwise we are just trading a trusted party for a wish.

2. The Yardstick: The Ideal World You Simulate#

In 1982, at Berkeley, Andrew Yao asked a question that sounds like a party riddle. Two millionaires want to know who is richer, but neither will reveal how much money he has. Can they learn the single bit "who is larger" and nothing else? Yao's paper turned that riddle into the founding question of a field: can a computation be as good as handing your inputs to a trusted party you never actually have to trust ^[3]?

The riddle exposes a harder question underneath. Suppose someone hands you a protocol and swears it "leaks nothing." How would you even check that claim? "Leaks nothing" is not a property you can eyeball in a transcript of messages.

The answer is the definition the entire discipline rests on, and it is worth stating carefully because every later construction is judged against it.

That is the whole trick of defining privacy: "secure" means "as good as a trusted party you never have to trust." The strongest version of this idea, universal composability, demands that the guarantee survive even when the protocol runs concurrently alongside arbitrary other protocols ^[4].

flowchart TB
subgraph REAL["Real world -- a protocol"]
ax[A holds input x] --> msgs[Rounds of protocol messages]
by[B holds input y] --> msgs
msgs --> rout[Output f of x and y]
end
subgraph IDEAL["Ideal world -- a trusted party"]
ax2[A holds input x] --> tp[Incorruptible trusted party]
by2[B holds input y] --> tp
tp --> iout[Output f of x and y]
end
adv[Adversary view in the real run] -. must be reproducible by .-> sim[Simulator given only the ideal output]

The definition also exposes the knobs every real protocol has to set. These choices, not raw speed, are what separate one construction from another.

Two more knobs matter. Fairness asks whether either everyone gets the output or no one does. Guaranteed output delivery asks whether honest parties are assured of the answer even if others quit. Both turn out to be luxuries you cannot always buy.

There is one caveat so important that misunderstanding it undoes everything. The guarantee is "nothing beyond the output," and the output itself can be revealing.

Keep one table open and fill it in as each construction arrives. Here it is seeded with the two anchors we already have: the ideal we are simulating, and Yao's special-purpose answer. Yao framed his 1982 result as the "millionaires' problem" precisely because a wealth comparison is the smallest interesting function whose output is a single bit yet whose inputs must stay hidden ^[3].

The definition says a trusted party can be simulated. It does not say how, or out of what. The smallest answer turns out to be almost insultingly humble.

3. The Engine: Oblivious Transfer, and Why One Primitive Is Enough#

In 1981, Michael Rabin described a primitive that sounds like a bug report. A sender transmits a message that the receiver gets with probability one-half, and the sender never learns whether it arrived ^[5]. Why would anyone want a channel that loses your mail at random and hides the tracking number from you?

Because that lossy, blindfolded channel turns out to be the entire trust engine of secure computation. The version everyone actually uses was pinned down by Even, Goldreich, and Lempel in 1985 and is cleaner to state.

sequenceDiagram
participant R as Receiver picks bit b
participant S as Sender holds m0 and m1
R->>S: blinded choice that hides b
Note over R,S: the sender cannot tell which message R wants
S->>R: encrypted pair only b can unlock
Note over R: R opens exactly the chosen message
Note over R: the other message stays unreadable
Note over S: the sender never learns b

Here is a toy version you can run. The parameters are tiny and the key-derivation is a stand-in, so this is illustration, not production cryptography, but the information flow is faithful: the receiver publishes two keys whose product is a fixed value, knows the secret behind only one of them, and can therefore open only the message it chose.

// Bellare-Micali-style OT with BigInt. Tiny params, toy key-derivation.
const p = 2147483647n;   // Mersenne prime 2^31 - 1
const g = 7n;
const C = 1234567n;      // fixed element; nobody knows its discrete log

function modpow(base, exp, mod) {
let r = 1n; base %= mod;
while (exp > 0n) { if (exp & 1n) r = (r * base) % mod; base = (base * base) % mod; exp >>= 1n; }
return r;
}
const inv = (a, mod) => modpow(a, mod - 2n, mod);   // Fermat inverse
const kdf = (x) => Number(x % 100000n);             // toy key-derivation

// Receiver: publish two keys with product C, but know the secret for pk[b] only.
function receiver(b, k) {
const pk = [0n, 0n];
pk[b] = modpow(g, k, p);
pk[1 - b] = (C * inv(pk[b], p)) % p;
return pk;
}
// Sender: verify pk0*pk1 = C, then mask each message with a key from pk[i]^r.
function sender(pk, m0, m1, r) {
if ((pk[0] * pk[1]) % p !== C) throw new Error("receiver cheated");
const gr = modpow(g, r, p);
return { gr, c: [m0 + kdf(modpow(pk[0], r, p)), m1 + kdf(modpow(pk[1], r, p))] };
}

for (const b of [0, 1]) {
const k = 987654n, r = 424242n;
const pk = receiver(b, k);
const { gr, c } = sender(pk, 111, 222, r);
const keyB = kdf(modpow(gr, k, p));        // = pk[b]^r, the only key R can form
console.log("receiver chose b=" + b + " -> recovered " + (c[b] - keyB) +
            "  (wanted " + (b === 0 ? 111 : 222) + ")");
}
console.log("to open the other message R would need the discrete log of C, which it lacks");

Now the earthquake. In 1988 Joe Kilian proved that oblivious transfer is complete: given a secure OT and nothing else, you can securely compute any function at all ^[7]. No additional cryptographic assumption is required. One blindfolded either-or choice is a universal building block, exactly the way a single NAND gate can express any Boolean circuit.

Kilian's completeness theorem is the reason the rest of this article is engineering rather than invention. You do not need a bespoke protocol for each function you care about. Secure oblivious transfer alone is enough to compute everything, so the whole problem reduces to building good OT and wiring it into circuits.

Oblivious transfer is to secure computation what NAND is to Boolean logic: one humble gadget, and everything else follows.

"Complete" is a theorem, not a performance promise, and the naive way to use it hits a wall immediately. Each OT, done from scratch, costs a public-key operation, the same expensive modular exponentiation you just watched. A circuit with a million AND gates would need on the order of a million public-key operations, which is far too slow to ship.

The fix is one of the quiet triumphs of the field. In 2003, Ishai, Kilian, Nissim, and Petrank showed how to extend oblivious transfer: starting from about 128 real base OTs, you can produce millions more using only fast symmetric-key operations, no further public-key crypto ^[8]. The IKNP trick inverts the roles of sender and receiver over a matrix of random bits, so that a mere 128 genuine OTs "bootstrap" an effectively unlimited supply. Later work tightened the constants for practical use ^[9]. The modern endpoint of that line is silent OT, where two parties expand short correlated seeds into vast amounts of OT-like randomness with almost no communication, resting on the learning-parity-with-noise assumption ^[10].

That engine is shared by the dishonest-majority constructions we turn to next, the garbled-circuit and secret-sharing lines. So one primitive suffices. But "suffices" is a theorem, not a blueprint. How do you actually turn blind one-of-two choices into a working joint computation? The field found three different answers at once, and, awkwardly for anyone who likes tidy stories, all three are still in use.

4. The Evolution: Three Ways to Instantiate the Trusted Party#

Between 1986 and 1988 the field produced three distinct general-purpose constructions with opposite trade-offs, and they coexist to this day. Read that sentence carefully, because the tempting story is wrong. This is a fork, not a ladder. Garbled circuits did not "evolve into" secret sharing, and none of the three is simply better than the others. In particular, and this is the single most-abused point in popular explanations, a garbled circuit is not a secret-sharing scheme. It is built from symmetric encryption and oblivious transfer.

If all three constructions can securely compute anything, why do all three still exist? Because each buys a different resource cheaply, and no application needs all resources at once.

timeline
title Simulating the trusted party, 1981 to 2026
1981 : Rabin introduces oblivious transfer
1982 : Yao poses the millionaires problem
1985 : Even-Goldreich-Lempel fix 1-out-of-2 OT
1986 : Yao garbled circuits, first general 2PC
1987 : GMW, anything is computable securely
1988 : BGW and CCD go information-theoretic, Kilian proves OT complete
1991 : Beaver triples split work into offline and online
2003 : IKNP OT extension makes OT cheap at scale
2012 : SPDZ, cheap malicious security at a dishonest majority
2024 : FROST standardized as RFC 9591
2026 : NIST IR 8214C calls for multi-party threshold schemes

Yao's garbled circuits: constant round, two parties#

Yao's 1986 construction was the first protocol that could securely compute any function of two parties' inputs ^[11]. Its shape is unlike anything in the secret-sharing world.

flowchart TB
g0[Garbler assigns two random labels per wire] --> g1[Garbler encrypts each gate truth table under input labels]
g1 --> g2[Send garbled circuit plus garbler input labels]
g2 --> ot[Evaluator obtains its input labels by oblivious transfer]
ot --> ev[Evaluator decrypts one row per gate and learns only output labels]
ev --> dec[Output labels decode to the result]

The defining virtue is round complexity. The garbler encrypts the whole circuit and sends it in one shot, the evaluator runs it locally, and the number of communication rounds does not grow with the circuit's depth. On a high-latency link between two continents, where each round-trip costs real milliseconds, that constant-round behavior is decisive.

The walls are just as concrete. The construction is inherently two-party. The entire garbled circuit must be transmitted, so communication grows with circuit size. And in its original form each AND gate cost four ciphertexts, one per row of the truth table, which point-and-permute lets the evaluator index directly ^[12]. The FOCS 1986 abstract of record is titled "How to Generate and Exchange Secrets," but the garbling construction itself is credited to Yao's oral presentation and later expositions, not spelled out in that short abstract. It is a mild historical irony that the most famous protocol in the field has no canonical originating paper for its own mechanism ^[11].

Those costs launched a decade of optimization. Free-XOR (2008) made every XOR gate cost zero ciphertexts by fixing a global offset between a wire's two labels ^[13]. Half-gates (2015) drove each AND gate down to two ciphertexts and proved that two is optimal for a broad class of linear garbling schemes, completing an arc from four to three to two ^[14].

BMR (1990) lifted garbling to n parties while keeping the constant-round property, by having all parties jointly garble one circuit ^[15]. And authenticated garbling reached malicious two-party security at roughly 37 milliseconds total, about 1 millisecond online and about 6.7 milliseconds amortized per AES block, which is fast enough to be unremarkable ^[16].

GMW: many parties, sharing plus OT, rounds that grow with depth#

A year after Yao, Goldreich, Micali, and Wigderson gave a different answer that scales to n parties ^[17]. Every wire value is split into XOR (additive) shares, one per party, that reveal nothing until combined. XOR gates are then completely local: each party XORs its own shares, no messages required. The cost lives entirely in AND gates.

Writing a shared bit x as the XOR of the parties' shares and likewise for y, the product x AND y expands into a sum of cross-terms, one for each pair of parties, and each cross-term is settled by a single oblivious transfer between that pair. Correctness for AND, privacy for everything, and the only cryptography in sight is OT.

// Split each bit into three XOR shares that reveal nothing on their own.
function share(bit) {
const s1 = Math.round(Math.random());
const s2 = Math.round(Math.random());
const s3 = bit ^ s1 ^ s2;          // the three shares XOR back to the secret
return [s1, s2, s3];
}
const reveal = (sh) => sh[0] ^ sh[1] ^ sh[2];

const x = 1, y = 0;
const X = share(x), Y = share(y);

// Each party XORs its OWN two shares locally. No messages are exchanged.
const Z = [X[0] ^ Y[0], X[1] ^ Y[1], X[2] ^ Y[2]];

console.log("shares of x =", X, " reveal ->", reveal(X));
console.log("shares of y =", Y, " reveal ->", reveal(Y));
console.log("local XOR of shares reveals ->", reveal(Z), " and x XOR y =", (x ^ y));
console.log("one share of x alone is", X[0], "-- a uniform bit, so it tells you nothing");

The trade-off is the mirror image of Yao's. Because each layer of AND gates needs a round of interaction, the number of rounds grows with the circuit's depth. On a fast local network that is fine; across a high-latency wide-area link, depth-many round-trips are the dominant cost. So the field already had two general constructions that were fast in exactly opposite conditions.

GMW also supplies the cleanest bridge to the previous post in this series. The base protocol is only semi-honest secure, but the GMW compiler upgrades it to malicious security by having every party prove, in zero knowledge, that each message was computed correctly from committed inputs and honest randomness. That is zero-knowledge proofs doing exactly the job Part 2 described, bolted onto MPC. The honest footnote is that generic per-gate zero-knowledge is concretely expensive, and in practice it was largely superseded by the SPDZ-style techniques we reach in the next section ^[1].

BGW and CCD: an honest majority buys unconditional security#

The third answer, from Ben-Or, Goldwasser, and Wigderson in 1988, and independently from Chaum, Crepeau, and Damgard the same year, dispenses with cryptographic assumptions entirely ^{[18, 19]}. Instead of XOR shares it uses Shamir secret sharing over a finite field, where each secret is a point on a random polynomial ^[20]. Addition of shared values is local, as before. Multiplication is the hard step: multiplying two degree-t sharings yields a product of degree 2t, which must be re-shared and its degree reduced back to t through a round of interaction. That degree-reduction step is the engine of BGW.

The security bounds are exact, and getting them right matters because they are widely misquoted. The completeness-theorem cluster is a genuine piece of conference drama: in the STOC 1988 proceedings, BGW (pages 1 to 10), CCD (pages 11 to 19), and Kilian's OT-completeness result (pages 20 to 31) sit on consecutive pages. Three foundational answers to "what is computable securely" arrived at one meeting ^{[18, 19, 7]}. BGW gives perfect privacy against a passive adversary that corrupts fewer than half the parties, t < n/2, and perfect privacy and correctness against a malicious (Byzantine) adversary corrupting t < n/3. Those thresholds are tight, and the malicious bound is t < n/3, not the "2t+1" that appears in careless summaries.

If you accept a negligible error probability and assume a broadcast channel, Rabin and Ben-Or later pushed the malicious threshold to t < n/2 ^[21]. The price of dropping all assumptions is the honest majority itself, plus heavy per-multiplication interaction.

The move that ties the modern secret-sharing world together came from Donald Beaver in 1991, and it is the reason "MPC is slow" is the wrong mental model.

Beaver triples split every secret-sharing protocol into a heavy, function-independent offline phase and a cheap, information-theoretic online phase. That shape is the direct ancestor of nearly all modern secret-sharing MPC, including the breakthrough in the next section.

With three constructions and one unifying trick in hand, the security ledger has filled out. Notice that it is not a ranking. Each row wins a different column.

The same coexistence, read as engineering trade-offs rather than a timeline, is the comparison every practitioner eventually internalizes.

flowchart TB
goal[Simulate the trusted party for any function] --> y[Yao garbled circuits]
goal --> g[GMW]
goal --> b[BGW and CCD]
y --> yt[Constant round, two parties, symmetric plus OT, dishonest majority]
g --> gt[Depth rounds, n parties, OT, dishonest majority given OT]
b --> bt[Depth rounds, n parties, no assumptions, honest majority]

Beaver triples make multiplication cheap, but the version described so far only holds against a passive adversary. For twenty years the practitioner's dilemma was that malicious security, a dishonest majority, and practicality were pick-two. Then one idea got all three at once.

5. The Breakthrough: Cheap Malicious Security at a Dishonest Majority#

Put yourself in the shoes of a practitioner around 2010. You can have information-theoretic security, but only with an honest majority you may not have. Or you can tolerate a dishonest majority, but only against a passive adversary, or by paying for a per-gate zero-knowledge compiler so expensive it is closer to a threat than a tool. The question that hung over the field was blunt: how do you catch a cheater who controls every party but you, without drowning in public-key cryptography?

SPDZ, from Damgard, Pastro, Smart, and Zakarias at CRYPTO 2012, answered it with a single idea ^[23]. The name is the authors' initials and is pronounced "speedz," which doubles as an accurate performance claim about its online phase. The idea is to authenticate every shared value so that tampering is caught the instant a value is opened.

Attach an information-theoretic message authentication code to every secret share. A single global MAC key, itself secret-shared and never revealed, guards all values at once. Any party that alters a share must forge a MAC it cannot compute, so one cheap check at the end catches a dishonest majority of active cheaters, and all the heavy cryptography hides in an offline phase that runs before any input exists.

Concretely, a global MAC key $\alpha$ is secret-shared and never opened. Every value x is stored twice over: the parties hold shares of x and shares of $\alpha \cdot x$, and linear operations preserve this relationship automatically. Multiplications consume authenticated Beaver triples generated offline, originally through somewhat-homomorphic encryption, later through oblivious transfer in the MASCOT variant and through faster homomorphic encryption in Overdrive ^{[23, 24]}.

At the end, a single MAC check verifies that nobody altered a value. To cheat undetected, an adversary would have to produce a valid MAC $\alpha \cdot (x + e)$ for an error e without knowing $\alpha$, which succeeds only with probability about $1/|\mathbb{F}|$ over the field. ※ With a 128-bit field that cheating chance is around $2^{-128}$, far below any threshold anyone worries about. Make the field large and that probability is negligible.

flowchart TB
subgraph OFFLINE["Offline phase -- input independent"]
o1[Manufacture authenticated Beaver triples] --> o2[Heavy crypto: SHE or OT]
end
subgraph ONLINE["Online phase -- cheap and information-theoretic"]
n1[Secret-share inputs with their MAC shares] --> n2[Evaluate circuit, consume triples]
n2 --> n3[One MAC check catches any tampering]
n3 --> n4[Open only the output]
end
OFFLINE --> ONLINE

The online phase is exactly the Beaver-triple trick, now doing real work. Here it is, running:

const P = 65537;                                   // work in a prime field
const mod = (a) => ((a % P) + P) % P;
const rnd = () => Math.floor(Math.random() * P);
const shareVal = (v) => { const s0 = rnd(); return [s0, mod(v - s0)]; };   // 2-party additive
const open = (sh) => mod(sh[0] + sh[1]);

// OFFLINE: one random triple ([a],[b],[c]) with c = a*b, made before inputs exist
const a = rnd(), b = rnd(), c = mod(a * b);
const A = shareVal(a), B = shareVal(b), C = shareVal(c);

// Secret inputs, secret-shared between two parties
const x = 12345, y = 54321;
const X = shareVal(x), Y = shareVal(y);

// ONLINE: open only d = x - a and e = y - b. Because a,b are uniform, these leak nothing.
const d = open([mod(X[0] - A[0]), mod(X[1] - A[1])]);
const e = open([mod(Y[0] - B[0]), mod(Y[1] - B[1])]);

// Each party forms its share of x*y locally:  [xy] = [c] + d*[b] + e*[a] + d*e
const Z0 = mod(C[0] + d * B[0] + e * A[0] + d * e);   // one party adds the public d*e
const Z1 = mod(C[1] + d * B[1] + e * A[1]);

console.log("opened only d = x - a and e = y - b:", d, e, "(uniform, reveal nothing)");
console.log("reconstructed x*y =", open([Z0, Z1]));
console.log("direct    x*y     =", mod(x * y));

The result is a protocol that securely computes any arithmetic circuit against up to n-1 malicious parties, with a cheap online phase and a single integrity check. It did not get superseded; it got refined. The SPDZ family is the current shape of general-purpose MPC, and the reference framework MP-SPDZ implements more than thirty protocol variants across the whole trade-off space ^{[25, 26]}. Modern offline phases increasingly draw their correlated randomness from silent OT, shrinking the preprocessing communication toward nothing ^[10].

The general-purpose ledger is now complete, with SPDZ as the entry that finally combined the three properties the field had spent two decades unable to get together.

SPDZ can securely compute any arithmetic circuit against almost everyone cheating. But most of the world does not need "any function." It needs exactly one function, over and over: sign this, or decrypt this. Fix the function, and something remarkable falls out.

6. The Deployed Special Case: Threshold Cryptography, Where No One Holds the Key#

Here is the reframing that pays off the whole article. Take the general machinery and fix the function f to just one operation: sign, or decrypt. Now the simulated trusted party has exactly one job, and its only output is a signature or a plaintext. If the key is never handed to anyone, where does it actually live?

The answer is that it never becomes a thing at all. Through distributed key generation, the private key is born as shares and is never reconstructed, not even at setup.

This is the sharp boundary with the sibling post, and it is worth drawing in bright lines, because the two ideas look similar and behave oppositely.

Threshold cryptography is not a separate subject from MPC. It is MPC with the function permanently fixed to "sign" or "decrypt." Everything in the first five sections applies, but because the function is fixed, the protocols can be specialized until they run in milliseconds, and the output is an ordinary signature any standard verifier accepts.

sequenceDiagram
participant P1 as Party 1 holds a share
participant P2 as Combiner holds a share
participant P3 as Party 3 holds a share
participant V as Any standard verifier
Note over P1,P3: distributed key generation, the private key is never assembled
Note over P1,P3: each party computes a partial signature from its own share
P1->>P2: partial signature one
P3->>P2: partial signature three
Note over P2: combine partials into one ordinary signature
P2->>V: a single standard signature
Note over V: verifies under the ordinary public key, blind to the sharing

The easy case is Schnorr. Because Schnorr signatures are linear, partial signatures simply add up, which makes the scheme friendly to thresholdize. FROST is the deployed standard here, and in 2024 it became RFC 9591, the first threshold-signature RFC, defining five ciphersuites and a two-round signing protocol ^{[27, 30]}. FROST stands for Flexible Round-Optimized Schnorr Threshold. The "round-optimized" part is the selling point: signing takes two rounds, and a preprocessing variant pushes the online phase to effectively one ^[30].

The hard case is ECDSA, and it is instructive precisely because it fights back. ECDSA signing requires multiplying two shared secrets and inverting a shared nonce, neither of which is linear, so thresholdizing it took real invention. Lindell made two-party threshold ECDSA practical in 2017 at roughly 37 milliseconds on the P-256 curve ^[31].

From there the deployed line split into two branches that still compete. One uses Paillier encryption for its multiplicative-to-additive conversion: GG18, its follow-up GG20, and the proactive, identifiable-abort CGGMP protocol that ships as Fireblocks' MPC-CMP ^{[32, 33]}. The other avoids Paillier entirely and does the multiplication with oblivious transfer: the DKLs line, two-party in 2018 and multiparty in 2019, tested to hundreds of parties ^{[34, 35]}.

Signing is not the only fixed function. Set f to decrypt and you get threshold decryption, where a ciphertext is jointly decrypted by share-holders without ever assembling the key, the pattern behind distributed key-management services and virtual hardware security modules. Victor Shoup showed as early as 2000 that a threshold of parties could produce standard RSA signatures without assembling the key ^[29], and Coinbase's open-source cb-mpc library is built for exactly this deployment ^[28].

The key is never a value in any box. It is a capability the group can exercise but no single member can hold.

There is one honest asterisk on all of this, and it points at the future. Almost every deployed threshold signature rests on the discrete logarithm, which a large quantum computer would break with Shor's algorithm. The framework itself can be post-quantum -- BGW needs no computational assumption at all -- but the keys people actually ship are not. That gap is precisely what NIST is now moving on.

With that, the special case takes its place as the final row of the ledger. The function is fixed, the output is a signature, and the "trust assumption" column now reads: the key is never assembled.

"No one holds the key" is not marketing. It is a property you can verify from the protocol. So where is it actually running today, and does the theory survive contact with production?

7. Where It Ships: Three Deployment Homes#

The theory is settled; the products are here. The discipline that keeps this section honest is to attribute every deployment by a chain: the scheme (a named protocol from a paper), the library that implements it, and the product that ships the library. Skip a link and you get the marketing gloss instead of the engineering.

The first home is MPC custody. When an exchange or bank holds cryptocurrency, the signing key is the whole ballgame, and a single server holding it is a single point of catastrophic failure. So custody vendors run threshold ECDSA. Fireblocks ships MPC-CMP, whose scheme is the CGGMP protocol from CCS 2020 and whose core is open-sourced as mpc-lib ^{[39, 33]}. "MPC-CMP" is named for the CGGMP protocol of CCS 2020 -- Canetti, Gennaro, Goldfeder, Makriyannis, and Peled -- not "Centralized Multi-Party" as a widely copied web gloss claims. Mind the initials: those five surnames spell CGGMP, while the bare acronym "CMP" is the three-author Canetti-Makriyannis-Peled line, so "CMP" should never be expanded to the five CGGMP names. The whole point of the design is that nothing is centralized ^[33].

Coinbase open-sourced cb-mpc, which packages threshold ECDSA, Schnorr, and EdDSA with DKG, OT, and zero-knowledge proofs ^{[28, 40]}. BitGo runs threshold ECDSA and EdDSA on the same never-reconstruct principle ^[41]. In every case the signing key is generated as shares and used without assembly.

That home also gives the series its sharpest cautionary tale, and it is the reason this post keeps insisting that an implementation bug is not a broken idea.

The second home looks nothing like the first. Private analytics gathers statistics from millions of devices without collecting anyone's individual data. Prio, from Corrigan-Gibbs and Boneh in 2017, is the template: each client splits its report into secret shares sent to a small number of non-colluding aggregators, which sum the shares and reconstruct only the aggregate, never any individual value ^[46]. ※ The privacy rests on the aggregators not colluding: any single aggregator sees only uniform-looking shares, so the guarantee holds as long as at least one of them is honest. Correctness is enforced by secret-shared validity proofs, so a malicious client cannot poison the total without detection.

This is aggregation-style MPC, quite distinct from garbled-circuit two-party computation, and it is being standardized at the IETF as the Distributed Aggregation Protocol (DAP) -- still a working-group draft -- while already running in production in ISRG's Divvi Up, alongside Apple and Google's Exposure Notifications analytics and Mozilla telemetry ^{[47, 48]}. These systems also add differential-privacy noise to the aggregate, a reminder that MPC protects the inputs while the output still needs its own defense ^[49]. Newer aggregation systems lean on function secret sharing, which splits a function rather than a value into two short keys, with the distributed point function as its point-query special case; Poplar uses exactly that to find frequent strings across many clients without a trusted aggregator, where Prio used plain additive shares ^{[50, 51, 52]}.

The most widely shipped special-purpose two-party computation is quieter than any of these. Private set intersection lets two parties learn only the elements their sets share, or an aggregate over those elements, and nothing else. Its clearest deployed form is privacy-preserving ad-conversion measurement, where Google's Private Join and Compute reveals only the size and value of an intersection and nothing about the individual records on either side ^[53]. Mobile contact discovery is the example people reach for, but it sharpens this article's thesis rather than illustrating it: the flagship privacy messenger, Signal, runs its production contact discovery inside an Intel SGX secure enclave with remote attestation ^[54] -- a trusted execution environment that trusts hardware, not a cryptographic two-party computation that trusts mathematics. Cryptographic private contact discovery has been demonstrated at scale as a research integration ^[55], yet messengers have not shipped it in place of enclaves. The construction mechanics are their own subject; the point here is that the flagship deployed 2PC is not a general circuit but this one tightly specialized function -- and where it genuinely ships, it ships as cryptography, not as hardware trust.

The third home is distributed key management. A conventional key-management service or hardware security module concentrates trust in one box; the threshold version spreads it. Coinbase's cb-mpc doubles as a distributed KMS ^[28], the virtual-HSM vendor Unbound was folded into Coinbase ^[56], and systems such as Zama's threshold key-management service keep decryption keys secret-shared, running sign and decrypt operations without ever reconstructing the full key ^[57]. The keys live only as shares, on purpose, from creation to retirement.

Every one of these systems made the same trade, and every trade has a price. It is time to be honest about the costs, and about the walls that no amount of engineering can move.

8. The Honest Costs and the Theoretical Limits#

If MPC can compute anything privately, why is not everything already private? The lazy answer is "MPC is slow," and it is the wrong frame. "Slow" implies a single number that hardware will eventually shrink to zero. The truth is more interesting and more permanent: the costs are a set of trade-offs, and beyond the trade-offs sits a set of theorems that no engineering will ever move.

Start with the trade-offs, because they explain why the field never crowned a winner. Rounds and communication pull against each other. Garbled circuits are constant-round but transmit the entire circuit, so they are bandwidth-hungry. Secret-sharing protocols send little per gate but interact once per layer of multiplication, so their round count grows with depth. Which one wins is not a property of the protocol; it is a property of the network.

On a wide-area link, where each round-trip costs tens of milliseconds, round complexity dominates and constant-round garbling pulls ahead. On a fast local network, bandwidth dominates and the lean secret-sharing protocols win. Add the security-model knobs from Section 2 -- semi-honest versus malicious, honest versus dishonest majority -- and the Yao/GMW/BGW/SPDZ trade-off table above becomes the real cost model. There is no single fastest MPC, only a fastest MPC for a given network and threat model ^{[2, 25]}.

Now the theorems, which are the deeper half of the story, because they say some of the ideal party's properties are simply unattainable.

The foundational limit is Cleve's, from 1986. He proved that complete fairness is impossible for general-purpose secure computation at a dishonest majority: no single protocol can fairly compute every function, because for some functions -- fair coin-tossing is the classic witness -- whichever party sends the last message can abort at the decisive moment and bias the outcome ^[58].

This is not a gap awaiting a cleverer protocol; it is a theorem. It is exactly why the SPDZ family, which aims at arbitrary circuits, provides security with abort rather than guaranteed output, so that "the protocol just stopped" is an accepted outcome rather than a bug.

Then the story turns, and the turn is the real insight of this section. Cleve rules out a protocol that is fair for every function; he does not rule out fairness function by function. Fairness is a property of the function f, not merely of the majority.

In 2008, Gordon, Hazay, Katz, and Lindell overturned the folklore that nothing is fair without an honest majority. They proved that a broad class of functions -- those with no "embedded XOR," which includes Boolean AND, Boolean OR, and Yao's millionaires' comparison -- can be computed with complete fairness even at a dishonest majority, and they gave an explicit two-party protocol that computes Boolean AND fairly with no honest majority at all ^[59]. An "embedded XOR" is a two-by-two block inside the function's truth table whose two diagonals are each constant and differ from one another, the pattern that makes plain XOR the canonical unfair function. AND, OR, and the millionaires' comparison contain no such block, which is precisely why they slip past Cleve's obstruction ^[59].

The fuller map -- which remaining functions are fair, and at what round cost, since some feasibly fair ones demand a super-logarithmic number of rounds -- was charted afterward by Asharov and by Asharov, Beimel, Makriyannis, and Omri. The credit for that characterization belongs to them, not to the 2008 result ^{[60, 61]}.

The other walls line up behind it. Information-theoretic security and guaranteed output require an honest majority, the perfect t < n/3 of BGW or the statistical t < n/2 of Rabin and Ben-Or with a broadcast channel ^{[18, 21]}. Oblivious transfer is both necessary and sufficient for dishonest-majority secure computation. Kilian proved the sufficiency: OT alone computes anything ^[7]. The necessity is the near-trivial converse, since OT is itself a two-party secure computation, so any protocol that computes arbitrary functions can in particular compute OT.

There is also a provable separation in communication cost: information-theoretic MPC must send data that grows with the circuit size, on the order of $\Omega(n \cdot |C|)$, while computational MPC built on threshold fully homomorphic encryption needs communication proportional only to the input and output sizes ^{[62, 63]}. That is not a gap someone will close; it is the price of dropping assumptions, stated as a lower bound. Two more limits round out the list: the output-leakage wall from Section 2, where even a perfect protocol reveals whatever the output implies, and the deployment-era wall, the discrete logarithm under almost every shipped threshold signature, which Shor's algorithm breaks and the NIST post-quantum threshold call targets ^[36].

The trusted party can be simulated arbitrarily well, but which of its ideal properties you keep depends on the function you compute and on how many parties you must distrust. An honest majority buys unconditional security and a guaranteed output. A dishonest majority forces cryptographic assumptions and, for general circuits, surrenders guaranteed output to Cleve's theorem -- yet even there, complete fairness survives for the specific functions that carry no embedded XOR. And no setting hides what the output itself reveals. There is no configuration that keeps every ideal property at once.

That reframes the whole picture. MPC is not "magic total privacy that happens to be slow." It is a provably bounded, trade-off-governed approximation of an ideal that is partly unattainable, function by function, and knowing exactly which part is unattainable is what separates an engineer from a marketer. These walls are permanent. But the frontier in front of them is very much alive, and the sharpest open question is the one a quantum computer will eventually force.

9. Open Problems: The Live Frontier#

The theoretical spine of MPC has been settled for decades, which makes its live edges easy to see. Five stand out, and the first is the sharpest.

Post-quantum threshold cryptography. The framework can be quantum-safe, but the deployed keys are not, and closing that gap is genuinely hard. Lattice signatures such as ML-DSA thresholdize awkwardly: their security relies on rejection sampling and carefully bounded noise, and splitting the signing operation across parties without leaking that noise, or aborting too often, is an open engineering problem. This is the explicit target of the NIST call, which places threshold ML-DSA in scope as an invited submission rather than a finished standard ^{[36, 37]}.

Collapsing the offline phase. SPDZ's throughput is bounded by how fast it can manufacture triples. Silent OT and pseudorandom correlation generators shrink the preprocessing communication toward sublinear, but their local computation cost and the exact parameterization of their underlying assumption remain active research ^[10]. The learning-parity-with-noise assumption behind silent OT is itself a candidate post-quantum assumption, which is why the modern offline phase and the post-quantum question are quietly related ^[10].

MPC at scale. Pushing to many parties and billion-gate circuits, with overhead approaching that of insecure computation, is a moving target. Honest-majority protocols now run close to the $\Omega(n \cdot |C|)$ communication lower bound, so further gains have to come from assumptions or from restructuring the computation rather than from cleverer sharing ^{[62, 63]}.

Resilient and asynchronous MPC. Delivering guaranteed output over real adversarial networks, where messages are delayed or dropped and parties may vanish, is possible only with an honest majority, because Cleve's theorem forbids it otherwise. Building practical asynchronous protocols that keep that guarantee is ongoing ^[58].

Standardization and interoperability. RFC 9591 gave FROST a single interoperable definition, but custody vendors still ship mutually incompatible threshold-ECDSA stacks. Whether the NIST effort yields interoperable post-quantum threshold standards, the way the IETF is standardizing private analytics through the Distributed Aggregation Protocol draft, is an open question with real commercial stakes ^{[27, 47]}.

Finally, the synthesis this series has been building toward. The three privacy technologies are complementary, not competing. Fully homomorphic encryption outsources computation on a single party's ciphertext. Zero-knowledge proofs establish correctness without revealing the witness. MPC splits trust across parties. The interesting systems compose them: MPC for input privacy, zero-knowledge for correctness against active cheaters, and homomorphic encryption to offload heavy computation. Threshold FHE already lives at exactly that seam, using MPC to distribute the FHE decryption key so that no party can unilaterally decrypt ^[63]. The frontier is not any one of these techniques winning; it is learning to wire them together.

The research is thrilling. But you have a system to ship this quarter, so here is how to choose today, without rolling your own cryptography.

10. A Practical Guide: Which Primitive, Which Library#

The decision is usually simpler than the theory. Match your problem to a construction, then reach for an audited implementation of it. Never write the protocol yourself.

flowchart TD
A{"What do you need?"} --> B{"Only sign or decrypt?"}
B -->|Yes| T[Threshold signatures: FROST, CGGMP, or DKLs]
B -->|No| P{"Just an intersection or an aggregate?"}
P -->|Set intersection| PSI[Private set intersection]
P -->|Aggregate over many clients| AGG[Prio or DAP, or DPFs for heavy hitters]
P -->|A general function| C{"How many parties?"}
C -->|Two parties on a WAN| G[Garbled circuits with half-gates]
C -->|Many parties on a LAN| D{"Honest majority available?"}
D -->|Yes| E[BGW-style, no assumptions]
D -->|No| F[SPDZ family, malicious at a dishonest majority]

The rules behind the fan are short enough to memorize. If two parties must jointly evaluate a mostly-Boolean function across a high-latency link, use garbled circuits with half-gates, upgraded to authenticated garbling if the adversary may be malicious ^{[14, 16]}. If many parties compute an arithmetic function on a fast network and you need malicious security, use the SPDZ family ^{[23, 25]}. If you have an honest majority and want no cryptographic assumptions, a post-quantum-safe framework, or guaranteed fairness, use a BGW-style protocol ^[18]. And if all you need is to sign or decrypt, use a threshold signature, FROST for Schnorr and EdDSA, CGGMP or DKLs for ECDSA, and do not build a general circuit for a job the specialized protocol does in milliseconds ^{[27, 33, 35]}.

Two specialized shortcuts finish the list. If two parties need only the intersection of their sets, or an aggregate over it, reach for private set intersection -- the flagship deployed 2PC, behind privacy-preserving ad-conversion measurement -- rather than a hand-rolled general circuit ^[53]. And for aggregate statistics across many clients with no trusted aggregator, use secret-shared reports in the Prio and DAP style, or function secret sharing and DPFs when you need private heavy hitters as in Poplar ^{[46, 52, 51]}.

The mature, audited frameworks are worth naming: MP-SPDZ spans more than thirty protocols across the trade-off space ^[26], EMP-toolkit is a reference for semi-honest and malicious garbling ^[64], and Fairplay, back in 2004, was the first general-purpose secure two-party system to leave the blackboard ^[65].

One decision table cannot answer every worry, so here are the questions readers ask most, and the misconceptions most worth retiring.

11. Frequently Asked Questions#

The Party Nobody Had to Be#

Return to the two hospitals and the billion-dollar transfer. The instinct in both cases was to appoint a trusted party, and the whole article has been an argument that you can get everything that party would have given you without anyone ever being it.

Read the evidence back in order. Kilian proved that one humble primitive, oblivious transfer, is enough to compute anything securely, which turned "invent a protocol per problem" into "build good OT and wire it up" ^[7]. Yao's garbled circuits, GMW, and BGW then instantiated that promise three different ways, trading rounds against bandwidth against trust assumptions so completely that all three still ship.

The preprocessing model and SPDZ made malicious security at a dishonest majority cheap, by authenticating every share so a single check catches a cheater ^[23]. And threshold cryptography is the deployed special case: fix the function to sign or decrypt, generate the key by distributed key generation, and the key exists only as a capability the group can exercise, never as a value in any box ^{[27, 28]}.

The honesty is the other half of the argument. MPC hides inputs, not outputs. Complete fairness for general-purpose computation is impossible at a dishonest majority, so a cheater can always halt, even though specific no-embedded-XOR functions stay fair even there. Information-theoretic security demands an honest majority. And almost every deployed threshold signature still rests on the discrete logarithm, which is why NIST's post-quantum threshold call, a call and not yet a standard, is the live frontier ^[36]. A companion post, "How Secure Multiparty Computation Would Break," presses on exactly those seams, and the series through-line remains that MPC, zero-knowledge, and homomorphic encryption are three complementary ways to compute on data that is never decrypted.

The trusted party can be simulated arbitrarily well. Which of its ideal properties you keep depends on the function you compute and how many parties you must distrust, and that, not speed, is the real shape of secure computation.