# The Trusted Party Nobody Has to Be: Secure Multiparty Computation and Threshold Cryptography, Where No One Holds the Secret
> Secure multiparty computation and threshold cryptography let distrusting parties compute on private data and sign with a key no single party ever holds.
*Published: 2026-07-20*
*Canonical: https://paragmali.com/blog/the-trusted-party-nobody-has-to-be-secure-multiparty-computa*
*© Parag Mali. All rights reserved.*
---
Secure multiparty computation (MPC) lets mutually distrusting parties jointly compute an agreed function over their private inputs while learning nothing but the output, as if an incorruptible trusted party ran the computation, except no one ever gets to be that party. One humble primitive, oblivious transfer, is provably enough to build it, and three classic constructions -- Yao's garbled circuits, GMW, and BGW -- trade rounds against bandwidth against trust assumptions in opposite ways. Threshold cryptography is the deployed special case: fix the function to "sign" or "decrypt," generate the key as shares, and it is used but never reassembled, which is why an MPC custody wallet can truthfully say no single box holds the key. The honest catch: MPC hides inputs, not outputs; complete fairness is provably impossible for general-purpose computation when most parties are dishonest; and most shipped threshold signatures still rest on the discrete logarithm, the gap NIST's post-quantum threshold call now targets.
## 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** [@lindell21-cacm].
A set of parties, each holding a private input, run a protocol that computes an agreed function and reveals only its output. No party learns anything about the others' inputs beyond what the output itself implies. The security goal is stated by comparison to an ideal world in which a trusted party collects the inputs, computes the function, and hands back only the result [@lindell21-cacm, @ekr-monograph].
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.
> **Key idea:** 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 [@yao82]?
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.
A protocol is secure if whatever an adversary can learn by participating in the *real* protocol, it could also have computed in an *ideal* world where a trusted party takes all inputs, evaluates the function, and returns only the output. Formally, a *simulator* given only the ideal-world output must be able to reproduce the adversary's entire real-world view. If it can, the real protocol reveals nothing the ideal output did not already imply [@lindell21-cacm, @ekr-monograph].
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 [@canetti01-uc].
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.
A *semi-honest* (honest-but-curious) adversary follows the protocol exactly but tries to infer private inputs from the messages it sees. A *malicious* (active) adversary may deviate arbitrarily: lie about its input, send malformed messages, or abort. Security against a malicious adversary is strictly harder and usually more expensive, and a protocol proven only semi-honest is worthless against an attacker willing to cheat [@lindell21-cacm].
In the *honest-majority* setting the adversary corrupts fewer than half the parties; in the *dishonest-majority* setting it may corrupt all but one. The distinction is not cosmetic: information-theoretic security and guaranteed output are possible with an honest majority, while a dishonest majority forces reliance on cryptographic assumptions and, as we will see, gives up the guarantee that everyone receives the answer [@ekr-monograph].
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.
> **Note:** MPC promises that parties learn nothing *beyond* the agreed output. It does not promise the output is safe. If two parties compute their sum, each learns the other's number by subtraction. If they compute "who is richer," the poorer party learns an upper bound on the richer one. Choosing a function whose output leaks too much is a design error no protocol can fix, and it is the single most common misconception about what MPC buys you [@lindell21-cacm].
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 [@yao82].
| What is hidden | Who computes | Adversary model | Parties | Rounds | Trust assumption |
|---|---|---|---|---|---|
| All inputs | One trusted party | None, by fiat | n plus a broker | 1 | Total trust in a single box (the thing we remove) |
| Both wealth values | The two parties themselves | Semi-honest | 2 | A few | A hardness assumption; no trusted party |
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 [@rabin81-ot]. 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.
The sender holds two messages, `m0` and `m1`. The receiver holds a choice bit `b`. After the protocol the receiver learns `m_b` and nothing about `m_(1-b)`, while the sender learns nothing about `b`. Two secrets are kept at once: the receiver's choice is hidden from the sender, and the unchosen message is hidden from the receiver [@egl85].
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 [@kilian88]. 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.
> **Key idea:** 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 [@iknp03].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 [@otext13]. 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 [@silentot19].
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 [@yao86]. Its shape is unlike anything in the secret-sharing world.
A Boolean circuit encrypted so it can be evaluated blind. The *garbler* assigns each wire two random labels, one standing for 0 and one for 1, then replaces every gate's truth table with encryptions keyed by the input-wire labels. The *evaluator*, holding exactly one label per input wire, can decrypt exactly one row of each gate and learns only an output label, never the underlying bit. The evaluator gets its own input labels by oblivious transfer, so the garbler never learns the evaluator's input. Garbling is symmetric encryption plus OT; it is not secret sharing [@yao86, @mit-ygc].
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 [@mit-ygc].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 [@yao86].
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 [@freexor08]. 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 [@halfgates15].
BMR (1990) lifted garbling to `n` parties while keeping the constant-round property, by having all parties jointly garble one circuit [@bmr90]. 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 [@wrk17-authgarbling].
### 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 [@gmw87]. 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](/blog/never-decrypted-proving-you-ran-the-computation-without-reve/) 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 [@lindell21-cacm].
### 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 [@bgw88, @ccd88]. Instead of XOR shares it uses Shamir secret sharing over a finite field, where each secret is a point on a random polynomial [@shamir79]. 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 [@bgw88, @ccd88, @kilian88]. 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` [@rabin-benor89]. 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.
A precomputed, secret-shared triple `([a], [b], [c])` where `a` and `b` are uniformly random and `c = a * b`, produced in an input-independent *offline* phase. In the *online* phase, multiplying two shared values `[x]` and `[y]` costs only opening `d = x - a` and `e = y - b`, then recombining locally. Because `a` and `b` are uniform, `d` and `e` reveal nothing about `x` and `y`, and the expensive work of making the triple happened before the inputs existed [@beaver91].
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.
| What is hidden | Who computes | Adversary model | Parties | Rounds | Trust assumption |
|---|---|---|---|---|---|
| All inputs | One trusted party | None, by fiat | n plus a broker | 1 | Total trust in a single box (removed) |
| Both wealth values | The two parties | Semi-honest | 2 | A few | A hardness assumption |
| Both inputs | Garbler and evaluator | Semi-honest to malicious | 2 (BMR: n) | Constant | Symmetric crypto plus OT; dishonest majority |
| All inputs | n parties on XOR shares | Semi-honest to malicious via ZK | n | Grows with depth | OT; dishonest majority given OT |
| All inputs | n parties on Shamir shares | Perfect, up to `t < n/3` malicious | n | Grows with depth | None; honest majority |
The same coexistence, read as engineering trade-offs rather than a timeline, is the comparison every practitioner eventually internalizes.
| Dimension | Yao garbled circuits | GMW | BGW / CCD | SPDZ family |
|---|---|---|---|---|
| Rounds | Constant | Grows with depth | Grows with depth | Cheap online, heavy offline |
| Communication | Whole circuit; 2 ciphertexts per AND (half-gates) | 1 OT per AND | Interaction per multiplication | Cheap online; heavy offline triples |
| Parties | 2 (BMR: n) | n | n | n |
| Majority | Dishonest | Dishonest, given OT | Honest (`t < n/2` passive, `t < n/3` malicious) | Dishonest (`n-1`) |
| Assumptions | Symmetric crypto plus OT | OT | None (information-theoretic) | Offline: SHE or OT; online: IT given the MAC key |
| Best suited for | 2PC on high-latency links | n-party Boolean on a LAN | Honest majority, no assumptions, fairness | Malicious n-party arithmetic |
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]
> **Note:** Yao's garbled circuits, GMW, and BGW are three different building blocks, not three rungs of one evolution. Garbled circuits use symmetric encryption and OT; GMW and BGW use secret sharing. They win in different network conditions and trust models, which is exactly why all three are still deployed almost forty years later. Any explanation that presents them as a single lineage has hidden the most useful thing about them.
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 [@spdz12].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.
> **Key idea:** 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 [@spdz12, @spdz2-12].
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.
A two-phase protocol structure. The *offline* (preprocessing) phase runs before any inputs are known and produces input-independent correlated randomness, such as authenticated Beaver triples, using the expensive cryptography. The *online* phase consumes that material to evaluate the actual function with cheap, mostly information-theoretic operations. Throughput is usually bounded by how fast the offline phase can manufacture triples [@spdz12, @beaver91].
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 [@mpspdz20, @mpspdz-github]. Modern offline phases increasingly draw their correlated randomness from silent OT, shrinking the preprocessing communication toward nothing [@silentot19].
> **Note:** When a modern system says it runs "maliciously secure MPC at a dishonest majority," it is almost always in the SPDZ family: authenticated secret shares, an offline triple factory, and a cheap online phase. Treat it as the baseline against which other choices are justified [@mpspdz20].
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.
| What is hidden | Who computes | Adversary model | Parties | Rounds | Trust assumption |
|---|---|---|---|---|---|
| All inputs | One trusted party | None, by fiat | n plus a broker | 1 | Total trust in a single box (removed) |
| Both wealth values | The two parties | Semi-honest | 2 | A few | A hardness assumption |
| Both inputs | Garbler and evaluator | Semi-honest to malicious | 2 (BMR: n) | Constant | Symmetric crypto plus OT; dishonest majority |
| All inputs | n parties on XOR shares | Semi-honest to malicious via ZK | n | Grows with depth | OT; dishonest majority given OT |
| All inputs | n parties on Shamir shares | Perfect, up to `t < n/3` malicious | n | Grows with depth | None; honest majority |
| All inputs | n parties on authenticated shares | Malicious, up to `n-1` corruptions | n | Cheap online, heavy offline | Offline crypto; online IT given the MAC key |
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.
Threshold cryptography splits a private key into shares held by `n` parties so that any authorized threshold of them can perform the secret-key operation, while fewer than the threshold learn nothing and the key is never assembled. *Distributed key generation* is the setup protocol that produces the public key together with a secret sharing of the matching private key, so the private key exists only as shares from the very first moment. The construction mechanics -- Lagrange interpolation at signing time, verifiable sharing, proactive refresh -- are developed in the companion [secret-sharing post](/blog/nobody-broke-shamir-a-field-guide-to-secret-sharing-and-thre/) [@rfc9591].
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.
> **Key idea:** 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.
A signature scheme split so that any authorized subset of `n` signers can jointly produce a signature that verifies under a single ordinary public key, while no smaller subset can sign and the private key is never reconstructed. To the outside world the result is indistinguishable from an ordinary signature; the sharing is invisible to the verifier [@rfc9591, @shoup00].
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 [@rfc9591, @frost20].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 [@frost20].
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 [@lindell17-ecdsa].
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 [@gg18, @cggmp20]. 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 [@dkls18, @dkls19].
| Dimension | Paillier-MtA (GG18 / GG20 / CGGMP) | OT-based (DKLs18 / DKLs19) |
|---|---|---|
| Multiplication primitive | Paillier MtA plus range proofs | Oblivious transfer, no Paillier |
| Rounds to sign | Multi-round; CGGMP has a non-interactive online phase | `log(t)+6`, two-party optimized |
| Communication | Lower bandwidth | Higher bandwidth from OT |
| Per-party compute | Heavier, Paillier operations | Lighter, symmetric and OT |
| Two-party signing time | Tens of milliseconds | Single-digit milliseconds on a LAN |
| Scale tested | Small to moderate `n` | Up to 256 parties, embedded devices |
| Extra features | Identifiable abort, proactive refresh, UC | Fewest assumptions |
| Known integration risk | TSSHOCK / BitForge in the range proofs | Newer analysis surface, no Paillier |
| Deployed in | Fireblocks MPC-CMP and many custody stacks | Wallet SDKs favoring Paillier-free designs |
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 [@shoup00], and Coinbase's open-source cb-mpc library is built for exactly this deployment [@cbmpc].
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](/blog/how-q-day-breaks-everything-shors-algorithm-and-the-simultan/). 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.
| What is hidden | Who computes | Adversary model | Parties | Rounds | Trust assumption |
|---|---|---|---|---|---|
| The private key itself | `n` share-holders | Malicious, scheme-dependent | n | 2 (FROST) to a few | Key never assembled; discrete-log hardness today |
"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 [@fireblocks-mpccmp, @cggmp20]."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 [@cggmp20].
Coinbase open-sourced cb-mpc, which packages threshold ECDSA, Schnorr, and EdDSA with DKG, OT, and zero-knowledge proofs [@cbmpc, @coinbase-mpc-blog]. BitGo runs threshold ECDSA and EdDSA on the same never-reconstruct principle [@bitgo-tss]. 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 [@prio17].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 [@ietf-dap, @divviup]. 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 [@enpa-whitepaper]. 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 [@dpf-gi14, @fss-bgi15, @poplar21].
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 [@psi-ion20]. 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 [@signal-pcd] -- 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 [@psi-kales19], 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 [@cbmpc], the virtual-HSM vendor Unbound was folded into Coinbase [@coinbase-unbound], 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 [@zama-tkms]. The keys live only as shares, on purpose, from creation to retirement.
| Workload | Scheme | Library | Product or deployment |
|---|---|---|---|
| Custody signing | CGGMP threshold ECDSA | Fireblocks mpc-lib | Fireblocks MPC-CMP |
| Custody signing | Threshold ECDSA, Schnorr, EdDSA | Coinbase cb-mpc | Coinbase custody and wallet services |
| Custody signing | Threshold ECDSA and EdDSA | Proprietary | BitGo |
| Private analytics | Prio secret-shared reports with validity proofs | libprio and DAP | Divvi Up, Exposure Notifications, Mozilla telemetry |
| Private set intersection | PSI (ad-conversion, aggregates) | Audited PSI protocols | Google Private Join and Compute |
| Private heavy hitters | Function secret sharing / DPFs | DPF-based (Poplar) | Heavy-hitter analytics without a trusted aggregator |
| Distributed KMS or virtual HSM | Threshold ECDSA and decryption | cb-mpc, Unbound, Zama TKMS | Custody KMS and virtual HSM offerings |
> **Note:** When you evaluate an "MPC" product, ask which named scheme its library implements and which paper defines that scheme. "We use MPC" is not an answer. "We run the CGGMP protocol with proactive refresh, or the DKLs OT-based protocol" is. The attribution tells you the trust model, the failure modes, and whether the code path that broke in TSSHOCK is even present [@cggmp20, @dkls19].
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 [@ekr-monograph, @mpspdz20].
Now the theorems, which are the deeper half of the story, because they say some of the ideal party's properties are simply unattainable.
A protocol computes a function with *complete fairness* if either all parties receive the output or none do, so no party can learn the answer while denying it to everyone else. This is strictly stronger than *security with abort*, in which a corrupted party may see the output and then quit before the honest parties obtain theirs. *Guaranteed output delivery* is stronger still: the honest parties are assured of the output even if the corrupted parties vanish entirely [@ekr-monograph].
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 [@cleve86].
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 [@ghkl08].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 *un*fair function. AND, OR, and the millionaires' comparison contain no such block, which is precisely why they slip past Cleve's obstruction [@ghkl08].
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 [@asharov14-fairness, @abmo15-fairness].
> **Note:** The tempting summary, "no function can be computed fairly without an honest majority," is false. Cleve's 1986 theorem forbids only a *single protocol that is fair for every function*; specific functions with no embedded XOR -- Boolean AND, OR, and the millionaires' comparison -- are completely fair even when every party but one is corrupt [@cleve86, @ghkl08]. General-purpose MPC still settles for security with abort precisely because it must also cover the functions, such as plain XOR, that Cleve's argument genuinely defeats.
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 [@bgw88, @rabin-benor89]. Oblivious transfer is both necessary and sufficient for dishonest-majority secure computation. Kilian proved the sufficiency: OT alone computes anything [@kilian88]. 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 [@dln-lowerbound, @asharov12-tfhe]. 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 [@nistir8214c].
> **Key idea:** 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 [@nistir8214c, @nist-mptc].
> **Note:** The most consequential open problem is not making MPC faster. It is making deployed threshold signatures quantum-safe. Today's custody keys rest on the discrete logarithm; a lattice-based threshold signature that is as efficient and as easy to implement as FROST does not yet exist. That is the gap NIST is now inviting the field to fill [@nistir8214c].
**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 [@silentot19].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 [@silentot19].
**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 [@dln-lowerbound, @asharov12-tfhe].
**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 [@cleve86].
**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 [@rfc9591, @ietf-dap].
Finally, the synthesis this series has been building toward. The three privacy technologies are complementary, not competing. [Fully homomorphic encryption](/blog/never-decrypted-how-fully-homomorphic-encryption-computes-on/) outsources computation on a single party's ciphertext. [Zero-knowledge proofs](/blog/never-decrypted-proving-you-ran-the-computation-without-reve/) 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 [@asharov12-tfhe]. 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 [@halfgates15, @wrk17-authgarbling]. If many parties compute an arithmetic function on a fast network and you need malicious security, use the SPDZ family [@spdz12, @mpspdz20]. If you have an honest majority and want no cryptographic assumptions, a post-quantum-safe framework, or guaranteed fairness, use a BGW-style protocol [@bgw88]. 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 [@rfc9591, @cggmp20, @dkls19].
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 [@psi-ion20]. 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 [@prio17, @poplar21, @fss-bgi15].
| Situation | Reach for | Audited implementation |
|---|---|---|
| Two parties, high-latency link, Boolean function | Garbled circuits (half-gates; authenticated garbling if malicious) | EMP-toolkit |
| Many parties, arithmetic, LAN, malicious security | SPDZ family | MP-SPDZ |
| Honest majority; no assumptions or fairness wanted | BGW-style (Shamir or replicated three-party) | MP-SPDZ honest-majority protocols |
| Only need to sign or decrypt | Threshold signatures (FROST, or CGGMP/DKLs for ECDSA) | cb-mpc, FROST implementations |
| Two parties, learn only a set intersection or an aggregate over it | Private set intersection (PSI) | Audited PSI protocols |
| Private aggregate stats across many clients, no trusted aggregator | Prio/DAP shares; FSS/DPFs for heavy hitters | libprio, DAP, Poplar |
| One server computes on your single ciphertext | Fully homomorphic encryption (Part 1) | See Part 1 |
| Prove a computation ran correctly | Zero-knowledge proofs (Part 2) | See Part 2 |
The mature, audited frameworks are worth naming: MP-SPDZ spans more than thirty protocols across the trade-off space [@mpspdz-github], EMP-toolkit is a reference for semi-honest and malicious garbling [@emp-toolkit], and Fairplay, back in 2004, was the first general-purpose secure two-party system to leave the blackboard [@fairplay04].
> **Note:** Three rules save you from the failure modes this series keeps circling. First, a protocol proven only semi-honest is worthless against an attacker who is willing to deviate; match the security model to your real adversary. Second, nonce and randomness hygiene is catastrophic to get wrong in threshold signing, so use vetted code paths. Third, keep GG18 and GG20 deployments patched: the TSSHOCK class of bugs lives in the range proofs bolted around the protocol, not in the protocol's core idea, and an unpatched library leaks keys even though the theorem is sound [@cve-2023-33241].
Suppose you run custody and want five of eight operators to authorize each transfer, with no server ever holding the key. Walk the fan. Do you only need to sign? Yes. So you do not build a general circuit at all. The asset uses ECDSA, so you choose a threshold-ECDSA protocol, CGGMP if you want identifiable abort and proactive refresh, or a DKLs OT-based protocol if you want to avoid Paillier machinery entirely, a line tracked on its public project page [@dkls-info]. You run distributed key generation so the key is born as eight shares, you require any five to sign, and you deploy an audited library rather than your own. The output is an ordinary ECDSA signature the blockchain verifies with the normal public key, and no box ever held the private key [@cggmp20, @dkls19].
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
No. Fully homomorphic encryption has one server compute on your single ciphertext, so trust rests on a hardness assumption. MPC splits the trust across several parties, so privacy holds as long as too few of them collude. They are different tools for different trust models, and they compose rather than compete [@lindell21-cacm].
No, and this is the most common misconception. MPC hides the inputs; the output is revealed to whoever is entitled to it, and the output can itself leak. If two parties compute their sum, each recovers the other's value by subtraction. Choosing a function whose output says too much is a design error no protocol can repair [@lindell21-cacm].
No. A Shamir backup is reconstruct-once: you gather the shares and rebuild the whole key to use it. An MPC signing key is never-reconstruct: it is used repeatedly without ever being assembled anywhere. That difference is the entire security claim of MPC custody [@rfc9591, @cbmpc].
The framework can be. BGW is information-theoretic and needs no computational assumption at all. But most deployed threshold signatures rest on the discrete logarithm, which Shor's algorithm breaks. NIST's IR 8214C places threshold ML-DSA in scope as an invited submission; it is a call for schemes, not a standardized scheme [@nistir8214c].
"Slow" is the wrong frame. The costs are trade-offs among rounds, bandwidth, and trust model, and the right choice depends on your network. Threshold signing in particular is millisecond-scale and ships in custody wallets today; general-purpose MPC has a cheap online phase after preprocessing [@ekr-monograph, @mpspdz20].
An honest majority is required only for information-theoretic security or a guaranteed output, which BGW gives at `t < n/3`; SPDZ-family protocols tolerate up to `n-1` malicious parties, a full dishonest majority, but only with security-with-abort, where a cheater can halt the protocol yet not forge the result [@bgw88, @spdz12]. Fairness is subtler. Complete fairness for *general* computation is impossible without an honest majority (Cleve), but fairness is a property of the function: specific functions with no "embedded XOR" -- Boolean AND, OR, and the millionaires' comparison -- are completely fair even at a dishonest majority, so the common claim that "no function is ever fair without an honest majority" is simply false [@cleve86, @ghkl08].
No. The fragility lives in the integration, not the theorem. TSSHOCK and BitForge extracted full keys from real wallets, but the flaw was a range-proof implementation bug, not a break of threshold ECDSA. Use audited libraries, keep nonce handling vetted, and patch GG18 and GG20 deployments [@cve-2023-33241].
## 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" [@kilian88]. 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 [@spdz12]. 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 [@rfc9591, @cbmpc].
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 [@nistir8214c]. 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.