No Cipher Fell: How Secure Multiparty Computation Would Break

1. The Protocol That Was Proven Secure, and Broke Anyway#

Three servers run a secure-computation protocol whose security proof you could check line by line: no shortcut, no weak cipher, no doubtful assumption. Two of them quietly compare notes, and in a single step the private input of the third lies exposed on the table. Nothing was decrypted, no key leaked, no oblivious transfer was broken. The proof still holds. It was simply a proof about a different world than the one the protocol was deployed into.

That scene is the whole article in miniature. Secure multiparty computation has no single "security level." It has a security relative to an adversary model, and every guarantee a deployment enjoys is conditional on three knobs plus one silent assumption: the corruption threshold (how many parties the adversary may control), the adversary's behavior (does it follow the protocol, or deviate?), the promised output guarantee (does everyone receive the answer, or can one party walk off with it alone?), and the quiet premise that protocol instances run one at a time.

Cross a threshold, face a more active adversary than you modeled, demand a fairness no protocol can give, or compose beyond your proof, and MPC breaks while the cryptography underneath stands perfectly still.

This is the closing entry of How It Would Break, and its structural sibling: we interrogate the model, not the machinery. The constructive companion, "Never Decrypted: MPC and Threshold," shows how that machinery is built and why it hides what it hides ^[3]. Here we take the machinery as sound and ask a narrower, sharper question: where does the guarantee actually live, and how do you kill it without touching a cipher? Four break families answer it, and each one closes on the same refrain -- no primitive fell.

If the proof is real and the primitives are sound, then the break must live somewhere the proof never promised to protect. Where, exactly, is that line?

2. The Line We Draw: What Counts as a Break#

We are going to break MPC on purpose, four different ways, without touching a single cipher. To keep that promise honest, we first have to draw a line, because the phrase "MPC broke" can point at two very different failures that are not our subject.

The first is a broken primitive. Someone cryptanalyzes the oblivious transfer, forges a commitment, predicts a pseudorandom generator, or runs Shor's algorithm against the discrete-log assumption under a deployed threshold signature. When a primitive falls, security can collapse below the corruption threshold, with an honest majority intact and every party following the rules. That is a real and catastrophic failure -- but it is a story about the primitive, and this article is not about the primitive.

The second is an implementation or side-channel failure: a timing leak, an injected fault, a biased random number generator, or a soundness bug in the glue code around a threshold signature. Here the mathematics is fine and the model is fine; the physical or coded realization leaks anyway. That is the province of the real-life sibling track, not this one.

What is left when you set both aside is the adversary-model layer: the definitions, thresholds, and guarantees that sit above the primitives. This is where we work. Everything below the line -- oblivious transfer, commitments, pseudorandom generators, Shamir secret sharing, the hardness assumptions -- we seal in a black box that behaves exactly as advertised. We allow ourselves one deep fact about that box: oblivious transfer is complete, so given a working oblivious transfer you can securely compute any function at all, even with no honest majority ^[4]. The box works. The question is what happens around it.

With the box sealed, here is the one-screen recap the rest leans on. In MPC, parties hold private inputs and want the output of a function on them while revealing nothing else. The gold standard for "nothing else" is an imaginary comparison: pretend a perfectly trusted outside party collected everyone's inputs, computed the function, and announced only the result. A protocol is "secure" if running it leaks no more than that ideal would ^[6].

Every break in this article is a way the real execution diverges from that imagined ideal -- and the ideal itself, as we will see, is a yardstick that can be set wrong.

So the primitives are sound and the side channels are someone else's chapter. That leaves the model. But to break a model, we first have to know precisely what it was promising -- and that promise turns out to be a measuring stick that can itself be mis-calibrated.

3. The Yardstick That Can Be Wrong: The Ideal, the Real, and the Five Properties#

Ask a cryptographer what "secure" means for MPC and you get a strange answer: it means as good as if a trusted outside party did it for you. The entire field is built on imagining a perfect stranger you do not actually have, and every break in this article is a way the imitation drifts from the imagination.

The power of this definition is also its fragility. "Secure" is defined against a specified ideal and a specified adversary. Write down a different ideal -- one that tolerates aborts, or fewer corruptions, or only passive eavesdropping -- and you have proven a different theorem. The proof is not wrong; it is answering a different question than the one your deployment asks.

Unpack that ideal and it decomposes into five distinct promises. Privacy: no party learns more about the others' inputs than the output already reveals. Correctness: the output really is the function applied to the actual inputs. Input independence: each party fixes its input without knowing the others'. Fairness: either everyone learns the output or no one does. Guaranteed output delivery, or GOD: the honest parties get the correct answer no matter what the adversary tries. A given protocol satisfies some subset of these, and which subset is set by the model, not by the quality of the code.

flowchart TD
G["A deployed MPC guarantee"] --> K1["Knob 1 -- Corruption threshold: how many parties may the adversary control"]
G --> K2["Knob 2 -- Adversary behavior: semi-honest, covert, or malicious"]
G --> K3["Knob 3 -- Output guarantee: delivery, fairness, or abort"]
G --> K4["Silent premise -- Composition: do instances run one at a time"]
K1 --> B1["Break Family I: cross the threshold"]
K2 --> B2["Break Family II: face a more active adversary than modeled"]
K3 --> B3["Break Family III: demand a fairness no protocol can give"]
K4 --> B4["Break Family IV: compose beyond the proof"]

Because each property is protected by a specific assumption, we can build a ledger and fill it in as we go. This table is the article's spine rendered as accounting: read the third column as the list of assumptions we are about to violate, and the fourth as what each violation looks like on the wire.

Look hard at the third column, because it hides the thesis. Every one of these guarantees is a theorem only relative to the assumption beside it. Change the assumption and the theorem does not merely weaken -- it becomes false. "Secure" is not a badge the protocol carries around; it is a relationship between the protocol and a model. Two sections from now we will watch a single secret-sharing scheme be perfectly private and then fully exposed, with nothing about the scheme changing except which side of a threshold we stand on.

One caveat belongs here before any break, because it is the property people most often imagine MPC has and it does not. MPC hides inputs, not outputs. Even a flawless protocol reveals the output, and the output can encode a great deal about the inputs: a two-party sum tells each party the other's number the instant they subtract their own ^[6]. That leak is irreducible, present in the ideal world itself, and no construction removes it. Keep it in mind, because it will return as a wall in the theory section.

If every property is only as true as its model assumption, then the history of MPC should read as a chronicle of those assumptions being set -- and mis-set. It does. And it begins with a fork built into the field on its very first day.

4. Two Founding Worlds, and the Threshold Baked In#

The wall that makes MPC break was discovered before anyone had built general MPC to break. In 1986, Richard Cleve proved a theorem about flipping a coin, and in doing so doomed a guarantee the field had not yet learned to want ^[8]. To understand why that inversion matters, it helps to walk the founding decade as what it actually was: not a race to faster protocols, but the adversary model coming into focus one assumption at a time.

It opens with a question. In 1982 Andrew Yao posed the millionaires' problem -- two people learn who is richer without revealing their wealth -- and, behind it, the general problem of computing on inputs nobody will share ^[1]. Four years later he gave the first general engine, garbled circuits, which made two-party secure computation concrete ^[9]. How that engine is built is the constructive sibling's story; here it is a sealed box.

The moment the question generalized from two trusting parties to many parties who might cheat, the field split in two, and it split along a threshold.

Goldreich, Micali, and Wigderson answered the "many cheaters" case in 1987 with How to Play Any Mental Game: a protocol tolerating up to $n-1$ corruptions -- any number of cheaters -- built by taking a semi-honest protocol and forcing every party to prove in zero knowledge that it followed the rules, the construction now called the GMW compiler ^[2]. The price of tolerating everyone-but-one was steep: the protocol is computational (it rests on hardness assumptions) and it is secure only with abort -- no promise that anyone actually receives the output.

A year later, Ben-Or, Goldwasser, and Wigderson took the opposite bargain. Their BGW protocol demands an honest majority and, in exchange, delivers perfect, information-theoretic security -- no computational assumptions at all -- with guaranteed output delivery, built directly on Shamir secret sharing ^[10]. Chaum, Crepeau, and Damgard reached the same frontier independently the same year by a different route ^[11].

Here is the framing fact the whole article rests on: from its first general day, MPC came in two feasibility worlds separated by a single threshold assumption. GMW's dishonest-majority world buys robustness against many cheaters and pays with abort. BGW's honest-majority world buys guaranteed delivery and perfect secrecy and pays with the requirement that most parties behave. Neither world is "more secure." Each is secure relative to a different adversary model, and the dividing line between them is a number: how many parties you concede to the adversary.

flowchart LR
Y1982["1982 -- Yao poses secure computation"] --> C1986["1986 -- Cleve proves fairness impossible in general, the wall, proved first"]
C1986 --> G1987["1987 -- GMW, dishonest majority, computational, with abort"]
G1987 --> B1988["1988 -- BGW and CCD, honest majority, information-theoretic, guaranteed output"]
B1988 --> UC["2000-2001 -- Canetti, stand-alone then Universal Composability"]
UC --> Ladder["2002-2014 -- the abort ladder, scoped by GHKL and Cohen-Lindell"]
Ladder --> Cost["2012-2018 -- the malicious-cost collapse, SPDZ, WRK, Chida"]

Two details are worth pinning before we push on. Chaum, Crepeau, and Damgard's CCD protocol is BGW's information-theoretic twin: same honest-majority feasibility frontier, reached independently by a different construction, published back-to-back with BGW in the 1988 proceedings ^[11]. Two teams arriving at the same boundary at the same moment is strong evidence the boundary is real, not an artifact of one design. And a name will recur so often it becomes a motif: a remarkable share of the load-bearing model-taxonomy results -- security without agreement, covert adversaries, efficient malicious 2PC, complete fairness, fairness versus delivery, the full BGW proof, cheap honest-majority malicious MPC -- carry Yehuda Lindell as a co-author ^{[12] [13] [14] [15] [16] [17] [18]}. The modern map of MPC's adversary model is disproportionately his lineage.

Two worlds, one dividing line: the corruption threshold. Everything the field learned afterward is a consequence of what happens when you stand on the wrong side of that line, or push straight past it. So let us push.

5. Break Family I: Crossing the Threshold#

This is the most fundamental break, and it hides a trap that catches almost everyone. Ask "what do you lose when the adversary crosses the corruption threshold?" and there are two different correct answers. Confusing them is exactly how careful engineers ship broken systems, so we are going to keep them rigorously apart. Two answers exist because there are two ways to be on the wrong side of a threshold, and they fail in opposite properties.

Mode (a): an honest-majority protocol pushed past its threshold#

BGW hides each secret as the constant term of a random polynomial of degree $t$, then hands each party one point on that polynomial ^[10]. The privacy is exact and conditional. As long as the adversary sees at most $t$ shares, those points are uniformly random and pin down nothing; the moment it sees $t+1$, the polynomial is fully determined and the secret drops out by interpolation.

The safe thresholds are precise: $t<n/2$ against a passive adversary, and $t<n/3$ against a malicious one. Those exact bounds -- and the malicious bound of $t<n/3$, not the "$2t+1$" people half-remember -- were pinned down by the full modern proof of the BGW protocol ^[17].

Push one share past the passive threshold and privacy is not degraded -- it is gone. The same scheme that was information-theoretically private a moment ago now spells the secret out in the clear.

flowchart LR
S["Secret s, hidden in a degree-1 sharing polynomial"] --> SH["Three points handed out, one share per party"]
SH --> ONE["Adversary controls 1 share -- all p lines still fit, one per candidate secret, privacy holds"]
SH --> TWO["Adversary controls 2 shares -- exactly one line fits, evaluate at zero, secret recovered, privacy gone"]
TWO --> MAL["Malicious adversary also injects a bad share into reconstruction -- too few honest points to correct it, output forced wrong, correctness gone"]

The demonstration below is the entire thesis compressed into thirty lines. A degree-1 Shamir sharing splits a secret across three parties. One share is consistent with every possible secret. Any two shares reconstruct it exactly. Nothing about the scheme changes between the two cases -- only how many shares the adversary holds.

// Shamir sharing over the prime field GF(p).
// Degree-1 polynomial f(x) = s + a*x  -- any 2 shares reconstruct s = f(0).
const p = 2087;
const mod = (x) => ((x % p) + p) % p;

const s = 1234, a = 777;          // dealer's secret and random coefficient
const f = (x) => mod(s + a * x);
const shares = { 1: f(1), 2: f(2), 3: f(3) };
console.log('shares handed out:', shares);

// ONE share: for any guessed secret, a matching line exists -> perfect privacy.
let consistent = 0;
for (let guess = 0; guess < p; guess++) {
const slope = mod(shares[1] - guess);       // makes f'(1) = share 1
if (mod(guess + slope) === shares[1]) consistent++;
}
console.log('secrets consistent with only share 1:', consistent, '(= p: all of them)');

// TWO shares: Lagrange-interpolate back to x = 0 and read the secret off.
const inv = (x) => { let r = 1, b = mod(x), e = p - 2;
while (e > 0) { if (e & 1) r = mod(r * b); b = mod(b * b); e >>= 1; } return r; };
function recover(pts) {
let secret = 0;
for (const [xi, yi] of pts) {
  let num = 1, den = 1;
  for (const [xj] of pts) if (xj !== xi) { num = mod(num * (0 - xj)); den = mod(den * (xi - xj)); }
  secret = mod(secret + yi * mod(num * inv(den)));
}
return secret;
}
console.log('recovered from shares {1,2}:', recover([[1, shares[1]], [2, shares[2]]]));
console.log('recovered from shares {2,3}:', recover([[2, shares[2]], [3, shares[3]]]));
console.log('true secret:', s, '-- the scheme kept its promise; only the assumption changed');

In the malicious regime a second guarantee is at stake. Once $t \geq n/3$, a corrupt party can inject a wrong share during reconstruction, and with too few honest points left to error-correct, the honest parties accept an output that is simply false. So the honest-majority world draws two thresholds against two different adversaries: against a passive adversary privacy survives up to $t<n/2$, while correctness against a malicious adversary is the stricter demand and gives out first, at $t<n/3$ ^[17].

This is the purest illustration of the article's claim, and the moment the first aha lands: "secure" was never a property the protocol had. The identical Shamir sharing is either perfectly private or fully exposed depending only on which side of a line the adversary stands. The primitive never moved. The assumption did.

"What collapses when you cross the threshold?" has two correct answers, and they are not the same. An honest-majority protocol pushed past its threshold loses privacy and correctness -- the shares reconstruct, and past the stricter $t<n/3$ bound a malicious party's injected errors go uncorrected. A dishonest-majority protocol run correctly never loses either; it surrenders fairness and guaranteed output delivery instead. Same word, "threshold," two entirely different breaks. Say which one you mean.

Mode (b): the dishonest-majority regime, handled correctly#

Now the other side of the line, and the half of the answer everyone forgets. GMW and SPDZ are built for a dishonest majority from the start. They tolerate up to $n-1$ corruptions, and when the majority does go bad they do not leak inputs and do not produce wrong outputs. Privacy and correctness both survive, with abort ^{[2] [19]}. Their security proof simply never promised more than "abort," so aborting is not a break of it.

What these protocols surrender instead is fairness and guaranteed output delivery -- and Cohen and Lindell proved that in the multiparty setting those are two genuinely distinct properties, not a single lump you lose together ^[16]. A dishonest-majority protocol can be fair for some functions yet still be haltable; it can guarantee neither in general. So "cross the threshold and you lose privacy" is at best half a truth. It describes mode (a) and badly misdescribes mode (b), where privacy and correctness are exactly what you keep.

So one "threshold break" is a privacy collapse and the other is a fairness surrender -- and the second happens only because a corrupt party can do something a merely curious one never would. Which turns the next knob: what if the adversary stops pretending to follow the rules at all?

6. Break Family II: The Adversary Who Won't Follow the Rules#

A protocol proven secure against an adversary who follows the rules tells you almost nothing about an adversary who does not. That is not a small gap to paper over -- it is a category error, and running a semi-honest proof against a malicious adversary is one of the most common ways real deployments break. The second knob is the adversary's behavior, and it has three settings.

The gap between semi-honest and malicious is not incremental; it is total. Yao's original garbled-circuit protocol is "only secure in the presence of semi-honest adversaries" ^[14]. Put a malicious party in the garbler's seat and it can garble a different circuit than the one agreed -- say, one that simply outputs the evaluator's private input -- and the evaluator, who only ever sees the result of whatever function it was handed, has no way to notice the substitution. The semi-honest proof did not get weaker; it was never a statement about this adversary in the first place.

Now the cost of closing the gap -- and here the folklore is badly out of date. "Malicious security is expensive" was true of the first construction and has been getting less true for twenty years. It is regime-dependent, not flat.

The original recipe was the GMW compiler: attach a zero-knowledge proof to every step, general and heavy ^[2]. For garbled circuits, Lindell and Pinkas built the first efficient malicious 2PC from cut-and-choose -- make many circuits, open a random subset to check honesty, evaluate the rest -- warning that "a naive implementation of the cut-and-choose technique ... does not yield a secure protocol" without input-consistency enforcement ^[14]. SPDZ shifted the model again: authenticate every shared value with an information-theoretic MAC and check before revealing output, catching cheating at the end rather than proving it at every step ^[19].

Then the penalty collapsed. In the honest-majority regime, Chida and coauthors drove malicious security to roughly twice the cost of semi-honest ^[18]. ※ That "twice" is a relative overhead against the same protocol's own semi-honest variant on the same circuit -- the price of adding a cheating-detection check -- not a fixed slowdown against some absolute baseline. In the dishonest-majority regime, authenticated garbling pushed the online cost to almost nothing: a maliciously secure AES evaluation in 37 ms total with a 1 ms online phase ^[21], and the same lineage scaled to AES among 128 parties across five continents in under three minutes ^[22].

On the arithmetic side, MASCOT produced malicious preprocessing at "less than 6 times" the semi-honest cost ^[23], and Overdrive's homomorphic preprocessing ran "6 times faster than MASCOT on a LAN and 20 times faster in a WAN" ^[24].

Read the bottom two rows together and the point of the table jumps out. The two dishonest-majority columns differ only on engineering axes -- how malicious security is priced -- and are identical on the guarantee axis. Their output guarantee is fixed by the threshold model, not by how cleverly or cheaply they buy active security.

Chida and coauthors achieve malicious security at roughly twice the cost of semi-honest -- and it is still "secure with abort and does not achieve fairness, meaning that the adversary may receive output while the honest parties do not" ^[18].

Which is the twist the cost story hides. You can make malicious security nearly free and still not get fairness, because fairness was never a matter of price. It was surrendered the moment you accepted a dishonest majority. And why it has to be surrendered is not an engineering shortfall at all. It is a theorem.

7. Break Family III: Learn-Then-Abort and the Fairness Impossibility#

Picture the simplest possible cheat. You run the protocol honestly, you receive your answer, and then -- before anyone else receives theirs -- you hang up. You learned the output; they did not. There is no cleverer protocol that stops you, and that is not for lack of trying. There is a proof that none can exist.

The third knob is the output guarantee, and this is where it turns. In any dishonest-majority protocol, there is a moment near the end when the output becomes reconstructible from the messages sent so far plus one more. Whoever is positioned to send that final message can compute the result first and then simply decline to send it.

sequenceDiagram
participant A as Alice (corrupt)
participant B as Bob (honest)
Note over A,B: A dishonest-majority protocol nears its final reconstruction round
A->>B: honest messages so far
B->>A: honest messages so far
Note over A,B: Decisive round -- one more message lets each side compute the output
B->>A: Bob sends his final share first
Note over A: Alice reconstructs the output now
A--xB: Alice aborts, withholds her final message
Note over B: Bob never gets the last share, receives no output
Note over A,B: Alice learned the result, Bob did not -- fairness broken, primitive intact

Why is a cheat this crude also this unstoppable? Because it is a theorem, and it was proved for the humblest function imaginable. In 1986 Richard Cleve showed that no protocol for flipping a single fair coin stays unbiased once at least half the parties can be faulty: whoever sends -- or withholds -- the last message can bias the outcome by aborting at the decisive round ^[8]. Since flipping a fair coin is just a very small secure computation, the corollary is sweeping: complete fairness is impossible, in general, without an honest majority ^[8].

The demonstration below makes Cleve's argument tangible. A two-party coin flip is supposed to be unbiased. But if one party learns the result one step ahead and may abort, she biases it -- not by breaking anything, only by refusing to send when she dislikes what she sees.

// A two-party "fair coin". The true bit is uniform. In the final round Alice
// learns it one step before Bob. If she may abort, Bob falls back to a guess.
function trial(aliceCheats, wants) {
const coin = Math.random() < 0.5 ? 0 : 1;    // the intended fair outcome
if (!aliceCheats) return coin;               // honest: Bob gets the true coin
if (coin === wants) return coin;             // she likes it -> she completes
return Math.random() < 0.5 ? 0 : 1;          // she aborts -> Bob's fallback guess
}
function rate(aliceCheats, wants, n) {
let ones = 0;
for (let i = 0; i < n; i++) ones += trial(aliceCheats, wants);
return (ones / n).toFixed(3);
}
const N = 200000;
console.log('honest run,            P(output = 1):', rate(false, 1, N), '(fair, ~0.5)');
console.log('Alice aborts to force 1, P(output = 1):', rate(true, 1, N), '(biased up, ~0.75)');
console.log('Alice aborts to force 0, P(output = 1):', rate(true, 0, N), '(biased down, ~0.25)');
console.log('No primitive was broken -- Alice only ever refused to send a message.');

This is the payoff of the chronological inversion from Section 4. Learn-then-abort is not an engineering weakness awaiting a fix, and no money spent on active security touches it, because it was proved impossible before general MPC was built. Spending on the behavior knob cannot buy back what the threshold knob gave away.

One guardrail keeps this insight from overshooting into a false universal. Cleve's result is "in general," not "always." In 2008, Gordon, Hazay, Katz, and Lindell overturned the folklore reading by proving that a broad class of functions can be computed with complete fairness even without an honest majority -- including Boolean AND and OR, Yao's millionaires' function, and any function without an "embedded XOR" ^[15].

So the correct statement is careful: complete fairness is impossible for some functions (those Cleve's argument reaches) at a dishonest majority, and perfectly possible for others. Anyone who says flatly "fairness is impossible without an honest majority" has overstated a theorem.

If complete fairness is off the table in general, the field faced a choice: give up, or define exactly what it could still guarantee. It chose the second. And what it built was a ladder.

8. The Ladder of Weakened Guarantees#

Every rung of this ladder is a concession, and the single most important thing about it is a distinction that people collapse constantly. The bottom rung -- selective abort -- is not the same thing as the impossibility that forced it into existence. One is the wound; the other is the scar. Keep them apart and the whole output-guarantee story snaps into focus.

Since complete fairness and guaranteed delivery are off the table at a dishonest majority, the field did the disciplined thing: it defined, precisely, a descending sequence of weaker guarantees and figured out exactly which are achievable where. The rule that orders them is simple: each step down drops exactly one guarantee.

flowchart TD
GOD["Guaranteed output delivery -- honest parties always receive the correct output, needs an honest majority"] --> FAIR["Complete fairness -- all or none learn the output, impossible in general at dishonest majority, possible for some functions"]
FAIR --> IDENT["Security with identifiable abort -- on abort, at least one cheater is publicly named"]
IDENT --> UNAN["Security with unanimous abort -- all honest parties agree, all get output or all get the failure symbol, but no cheater is named"]
UNAN --> SEL["Security with selective abort -- the adversary picks which honest parties get output and which get the failure symbol"]

Walk down the rungs and watch each one shed a single promise. Guaranteed output delivery is the top, and it needs an honest majority. Complete fairness sits just below -- weaker than delivery because it permits an all-or-nothing failure, and impossible in general below an honest majority though possible for some functions.

Now fairness is gone and we are living with abort, where three rungs remain. The strongest is identifiable abort, the rung Ishai, Ostrovsky, and Zikas formalized: if the protocol aborts, it must name a cheater, so a malicious party can no longer stall the protocol anonymously and forever ^[25].

Drop the naming and you get unanimous abort: the honest parties still agree -- all receive the output, or all receive the failure symbol together -- but the abort is anonymous. Drop even the agreement and you reach the floor, selective abort, where the adversary not only aborts but chooses which honest parties get the answer and which get nothing ^[12].

Identifiable abort therefore sits above unanimous abort, not below it: it is unanimous abort plus a named cheater, so it strictly implies the weaker rung. Reversing the two -- a common slip -- gets the concession structure exactly backwards.

Guaranteed delivery is what an honest majority buys. Selective abort is what a dishonest majority leaves you. Everything in between is the field negotiating with a theorem.

Now the clarification the whole section exists to make. It is tempting to treat "selective abort" and "the fairness impossibility" as two names for one idea. They are not. The fairness impossibility (Cleve) is the cause: a proof that you cannot have all-or-nothing delivery at a dishonest majority. Selective abort (Goldwasser-Lindell) is the consequence: the strongest guarantee the field could still define and achieve once fairness was ruled out ^{[8] [12]}. Reason and result. Confusing them makes it sound like selective abort is a kind of impossibility, when it is actually the field's constructive answer to one.

Selective abort is the consequence; Cleve's impossibility is the cause. The entire abort ladder exists because complete fairness is impossible in general at a dishonest majority. Selective abort is not a restatement of that impossibility -- it is the achievable floor the field engineered in response to it. And the ladder is ordered: identifiable abort ranks above unanimous abort, because it adds a named cheater. Reason and consequence, never synonyms.

Threshold, behavior, output guarantee -- three knobs, three break families. But there is a fourth break, subtler than all of them, that a "primitives are sound" audit sails straight past: the protocol that is perfectly secure by itself and breaks the instant you run two copies of it.

9. Break Family IV: Input Substitution and the Composition Trap#

The subtlest breaks do not cross any threshold and do not need a malicious garbler. They exploit the gap between what your proof covered and what your deployment actually did, and they are the ones that pass every audit -- because nothing cryptographic fails at all.

Start with a definition that is easy to get backwards. A corrupt party is always allowed to choose its own input. If a bidder lies about its valuation in a sealed-bid auction, that is not an MPC break -- the ideal trusted party would have accepted the lie too. Canetti's stand-alone definition captures this precisely: the simulator extracts an "effective input" from the corrupt party and feeds it to the ideal function, so free choice of some input is inherent and harmless ^[7].

The break is not free choice; it is dependence. If a corrupt party can arrange for its input to be a function of an honest party's input -- "bid exactly one dollar more than whatever she bids" -- then the ideal world, where inputs are committed independently before anything is computed, has been violated. And here is the trap: a protocol can be perfectly secure against this on its own and lose the property the moment two copies run at once.

That is because stand-alone security does not compose. Canetti's Universal Composability framework exists precisely to name and fix this gap: a protocol proven secure in isolation can fail when many instances run "in the presence of an unbounded number of arbitrary protocol instances that run concurrently in an adversarially controlled manner" ^[26]. A man-in-the-middle who cannot break a single session can still relay and maul messages between two sessions, wiring a corrupt input in one to an honest input in the other.

sequenceDiagram
participant A as Alice (session 1)
participant M as Mallory (man in the middle)
participant B as Bob (session 2)
Note over A,B: Two instances run concurrently, each proven stand-alone secure
A->>M: Session 1 message carrying a commitment to input a
Note over M: Mallory does not open it -- she relays and mauls it
M->>B: Session 2 message, mauled so her input becomes a function of a
B->>M: Session 2 continues, its output now depends on Mallory's input
Note over M: Mallory's input depends on Alice's -- input independence broken
Note over A,B: No cipher failed, no threshold crossed -- the proof never covered two sessions

This is the break family with the smallest footprint and the widest blast radius. Nothing you could point at is broken. Every commitment still binds, every cipher still holds, every zero-knowledge proof still verifies, and the corruption threshold was never approached. What failed is upstream of all of that: the definition was proved for a single isolated execution and then silently reused for a deployment that runs many at once.

So for the fourth time the refrain holds, and this time it holds in the hardest case: no cipher fell. A corrupt party made its input depend on an honest one, an honest deployment ran two sessions its proof never mentioned, and the security guarantee evaporated with every cryptographic component still working perfectly.

Four break families, four mis-set knobs, and a pattern so consistent it stops looking like coincidence and starts looking like a law. It is time to line them all up in one table -- and read the column that says the same word in every row.

10. The Master Table: Every Break Is a Model Violation#

Here is the payoff. Four break families, five properties, and one yes-or-no column that compresses the whole article into a single sentence. Read the table row by row, then read the last column top to bottom.

The last column is the argument. In every row where the model was mis-set, the primitive column reads no. The one row where it reads yes is the row this article deliberately set aside in Section 2 -- a cryptanalyzed oblivious transfer or commitment, or Shor's algorithm against the discrete-log assumption beneath a deployed threshold signature. That route is real and catastrophic, and it is a genuinely different kind of failure: it can break security with the model perfectly set, every party honest, and the threshold respected.

Naming it and stopping is not a dodge; it is the honesty the thesis requires. The claim was never "MPC cannot be broken." It was "MPC's structural breaks live in the model, not the machinery," and the table is that claim rendered as evidence.

Every structural break is a model violation. Line up the four families and the "primitive touched?" column reads no in every row -- privacy from crossing a threshold, fairness from an abort, input independence from composition, none of it requiring a single cryptographic component to fail. Scoped to the adversary-model layer, with primitives assumed sound, the break is the assumption, not the primitive. The only row that reads yes is the primitive route this article hands off.

That is the third and deepest aha. One section at a time, the breaks looked like a grab-bag of unrelated attacks -- a threshold here, a garbled circuit there, a dropped message, a doubled session. Seen together they are one phenomenon in four costumes: each a knob turned to a setting the deployment could not enforce, each leaving the cryptography untouched. The diversity was an illusion of altitude; from high enough up, there is one break.

MPC's security is only as real as its adversary model. The break is the assumption, not the primitive.

If every break is a mis-set knob and not one is a broken cipher, a hopeful thought arises: surely a cleverer protocol could just fix them? For the shallow breaks, engineering helps. For the deep ones, no -- and the reason is that they are not shortfalls waiting on a better idea. They are walls, proven and load-bearing. To those walls we turn next.

11. The Walls That Make These Breaks Unavoidable#

The difference between a bug and a wall is that you can fix a bug. Almost everything in this section is a wall: proven, load-bearing, and on the axes that matter, tight -- meaning the best protocol we know how to build and the best protocol that could ever exist meet at exactly the same line. Where a limit is instead merely an open engineering problem, the table says so, because conflating the two is its own kind of error.

Start with the permanent walls, each tagged with its epistemic class so you can tell a theorem from a to-do list.

Every wall in the top group has the same shape: each is a counting fact about who can be corrupted or who can abort last, never a statement about a primitive's strength. Cleve's bound counts who sends the final message ^[8]; the BGW thresholds count how many honest evaluation points survive to error-correct a cheater's shares ^[17]; even the residual leak is a counting fact about information, since revealing a function of the inputs reveals something about them, and no protocol can announce the answer while hiding it ^[6].

On the feasibility spine the gap is closed: BGW achieves the thresholds Cleve and the necessity results forbid anyone to beat, and the dishonest-majority ceiling of malicious-with-abort up to $n-1$ is tight against Cleve. No cleverer construction is coming to make a dishonest-majority protocol fair for a general function -- that door is shut by theorem, not by the state of the art.

The open problems are refinements, not feasibility questions, and they split by type. Making UC-secure protocols concretely cheap is engineering: composable security is proven, but its overhead over stand-alone security is steep, so practitioners who cannot pay it inherit the composition break of Section 9 ^[26].

Characterizing exactly which functions are completely fair without a majority is theory: GHKL proved the class is broad, but its precise boundary between Cleve's "impossible" and their "possible" is unmapped ^[15]. Efficient guaranteed delivery at scale is engineering: Fantastic Four reaches delivery for four parties without a single trusted delegate, but fault-tolerant delivery for large party counts is still a frontier ^[27].

And then the fourth open problem, which is not really ours at all.

There is no single "secure." There is only secure relative to an adversary model you can enforce -- and the ideal protocol is the correct match, not a universal primitive.

The walls are fixed and, where they matter, tight. That is oddly good news. It means the practitioner's job is not to out-clever a theorem but to read the knobs correctly and deploy the protocol that matches the model they can actually enforce. So how do you keep from being the break?

12. How Not to Be the Break#

Every break in this article was, at bottom, somebody deploying a protocol into a world its model did not describe. The reassuring corollary is that avoiding them is a checklist problem, not a genius problem. You do not need a new theorem. You need to state the model you are actually in and pick the protocol that matches it. Here is that checklist, each item pointing back to the section that earned it.

State your adversary model explicitly, then match the protocol to it. Write down three things before choosing any construction: the corruption threshold you face (honest or dishonest majority), the adversary's behavior (semi-honest, covert, or malicious), and the output guarantee you need (abort, fairness, or delivery). The overwhelming majority of real breaks are a mismatch between one of these and the protocol's proof, not a broken primitive. The decision guide below is that matching made mechanical.

flowchart TD
Q1{"Can you enforce an honest majority?"}
Q1 -->|Yes, and you need liveness| HM["Honest-majority secret sharing -- you may promise guaranteed delivery"]
Q1 -->|No| DM{"LAN or WAN?"}
DM -->|LAN, arithmetic| SP["SPDZ-family authenticated secret sharing -- accept security with abort"]
DM -->|WAN or many parties, Boolean| AG["Constant-round authenticated garbling -- accept security with abort"]
HM --> DoS{"Is one-party denial-of-service a business risk?"}
SP --> DoS
AG --> DoS
DoS -->|Yes| IDA["Prefer identifiable abort, or delivery if you have an honest majority"]
DoS -->|No| COMP{"Do instances run concurrently?"}
IDA --> COMP
COMP -->|Yes| UC["Use UC-secure building blocks"]
COMP -->|No| DEP["Match the behavior knob, then deploy an audited framework"]

Never deploy a semi-honest protocol where inputs are adversarial. A semi-honest proof is not a weak form of malicious security; it is a statement about a different adversary and gives you nothing against one who deviates ^[14]. If a participant has any incentive to cheat, you need at least covert and probably malicious security.

Choose a threshold you can architecturally enforce. If you cannot guarantee an honest majority, accept security with abort and use a dishonest-majority protocol built for it -- GMW or the SPDZ family, including SPDZ2k for arithmetic over machine integers modulo $2^k$ ^{[19] [30]}. Only buy guaranteed delivery with honest-majority secret sharing if you can make the majority true through separate operators, jurisdictions, or hardware ^{[31] [18] [27]}. A threshold you merely hope holds is Break Family I waiting to happen.

Match the network and the data type. Honest-majority secret sharing and SPDZ-style protocols are strong on a LAN; for a wide-area network or many geographically spread parties, constant-round authenticated garbling pays its higher bandwidth to save round trips ^[22]. Arithmetic workloads favor secret sharing (and mixed frameworks like ABY3 for privacy-preserving machine learning); Boolean workloads favor garbling ^[32].

Prefer identifiable abort where one-party denial-of-service is a business risk. If a single participant halting the computation is a real operational threat, plain selective abort is a liability. Reach for identifiable abort so an aborting cheater is named, or for guaranteed delivery if you hold an honest majority ^[25].

Use UC-secure building blocks when instances compose. If your MPC runs as a sub-routine, or many sessions interleave, stand-alone proofs do not cover you. Use universally composable components, or you inherit the composition break directly ^[26].

Never claim fairness you have not proven, and never roll your own. Do not promise fairness without an honest majority or a proof that your specific function lies in the fair class ^[15]. And do not hand-build any of this: reach for audited frameworks -- MP-SPDZ across the honest/dishonest and semi-honest/malicious grid, EMP-toolkit for authenticated garbling -- and lean on the practitioner literature that maps the tradeoffs ^{[33] [34] [35] [36]}.

Remember the routes this article handed off. Even a perfectly model-matched deployment can still fall to a broken primitive or a side channel. Use post-quantum-safe primitives wherever Shor is a threat to your threshold signatures ^[28], and treat the implementation surface -- timing, faults, randomness -- as its own separate audit.

The reflex to distrust is the cryptography. The discipline to master is the model. Get the knobs right and MPC is one of the most powerful tools we have; get one wrong and no proof will save you -- because the proof was never about the world you deployed into.

13. Frequently Asked Questions, and a Last Word#

So the story closes where it began, with a proof that held and a system that failed anyway. Across four break families the primitive column read no every time: privacy fell to a crossed threshold, correctness to a corrupted reconstruction, fairness to a withheld message, input independence to a doubled session -- and not one oblivious transfer, commitment, or secret-sharing scheme was ever broken.

MPC has no absolute security level. It has a security relative to an adversary model, and the deep discipline of deploying it is not distrust of the cryptography but precision about the model you can actually enforce.

For how the machinery this article sealed in a black box is actually built -- the secret sharing, the oblivious transfer, the commitments that never fell -- see the constructive companion, Never Decrypted: MPC and Threshold ^[3]. And Part 12 of this series, A Valid Proof of a False Thing, tells the same story one layer down in zero-knowledge proofs, where a valid proof of a false statement is likewise never a broken cipher but a mis-set model.

The pattern, by now, should feel inevitable: when cryptography breaks in the ways this series studies, look first not at the math, but at the assumption the math was answering.