Secure Multiparty Computation

Two millionaires meet and each wants to know who is richer. Neither will state a number. Written as a computation, they hold $x_1, x_2 \in \mathbb{N}$ and want

History. Andrew Yao posed the millionaires' problem in 1982 in "Protocols for Secure Computations"; the garbled-circuit construction of §8 followed in 1986.

and nothing more. Without a secure protocol, one party must reveal its input or both parties must entrust their fortunes to an intermediary that could lie about the result.

The variant with three parties makes the leak in the output itself visible. Three colleagues want the maximum of their salaries, $f(x_1, x_2, x_3) = \max(x_1, x_2, x_3)$, with no salary revealed. A perfect protocol still leaks what the output says: whoever earns the maximum sees their own salary come back as the answer and learns they hold it, while the other two learn only that they do not. That much is in the function, so no protocol can remove it.

The same shape recurs across applications.

• Secure dating computes $y = x_1 \wedge x_2$, so a one-sided attraction is never disclosed.
• Coin tossing outputs a value $y$ uniform on $\bits$ that neither party can bias, a functionality with no inputs at all.
• Digital auctions compute the winner and the clearing price from sealed bids; electronic voting computes a tally from ballots.
• Online poker deals a shuffled deck no player can see; cloud computing lets a server compute on data it never learns.
• Private set intersection lets two parties learn which of their records match and nothing about the rest, the same problem for a set-valued function.

History. The auction became real commerce in 2008, when Danish sugar beet contracts were traded in the first large commercial multiparty auction, with 1229 farmers bidding.

Formally, $n$ parties $P_1, \dots, P_n$ hold inputs $x_1, \dots, x_n$ and evaluate an $n$-input, $n$-output function $f(x_1,\dots,x_n) = (y_1, \dots, y_n)$, with $P_i$ receiving only $y_i$. The function may also be randomized.

With an incorruptible trusted party the problem is trivial: everyone sends its input up, the trusted party evaluates $f$ and sends each $y_i$ down. That is the ideal world, the standard against which any real protocol is measured. The real world has only the $n$ parties and a network among them.

Take a sealed-bid auction and enumerate what an attacker might want. Five properties cover the list.

• Privacy. Nothing beyond the prescribed output is revealed; the attacker may want to learn the other bids.
• Correctness. Each honest party receives the value the function actually prescribes on the inputs used; the attacker may want to win with a bid below the highest.
• Independence of inputs. A corrupted party cannot choose its input as a function of an honest party's input; the attacker may want to set its bid after seeing the others.
• Fairness. If one party receives the output, all do; the attacker may want to walk away once it sees it has lost.
• Guaranteed output delivery. Corrupted parties cannot prevent honest parties from receiving the output. This is strictly stronger than fairness, which a protocol in which nobody gets anything also satisfies.

Enumerating properties per application is a losing strategy: for elections the list shrinks to privacy, correctness and fairness. There is never an argument that any list is complete. The chapter instead adopts a single general definition (§3), once the adversarial model is pinned down.

The Power of the Adversary

A threshold adversary corrupts a set of at most $t < n$ parties. The adversary is taken to be monolithic, a single entity coordinating all corrupted parties, which is the right model because separate corrupted parties can always collude. Corruption is non-adaptive (static) when the corrupted set is fixed before the protocol starts, and adaptive when it is chosen during the execution, based on what the adversary has seen. The behavioral axis is a ladder: each rung allows more deviation and costs more to defend against. The ladder and the two corruption thresholds used later in the chapter, with the attacker's capability beside each:

The Execution Setting

Standalone security considers a single execution in isolation and, as a theorem, extends to sequential composition. It does not cover the Internet, where many instances of a protocol run concurrently alongside arbitrary other protocols. Concurrent composition covers many instances of the same protocol; universal composability (Canetti, 2001) covers arbitrary concurrent protocols and is the real goal.

Define security by comparison: a protocol is secure if running it is as good as handing the inputs to the trusted party. Anything an adversary achieves in the real execution it could already have achieved in the ideal world, where by construction the only freedom it has is to choose its own input. The comparison is made through a simulator. Consider first the semi-honest two-party case, with $f(x_1,x_2) = (f_1(x_1,x_2), f_2(x_1,x_2))$.

Read the definition as an argument. The simulator is given only what the corrupted party is entitled to, namely its own input and its own output. If it can nevertheless produce a transcript indistinguishable from the real one, then everything the adversary learned was already derivable from its input and output alone. In the semi-honest model correctness, independence of inputs and fairness need no separate treatment, because the adversary follows the protocol and the inputs are well defined.

Against malicious adversaries, simulating the view is insufficient. A malicious party's messages need not correspond to running the protocol on any $x_2$ at all, and view simulation says nothing about correctness, independence of inputs or fairness. The repair is to make the ideal world explicit: the ideal-world adversary may substitute an input $x_2'$ of its choosing (and that is all it may do), and security requires that the joint distribution of the honest party's output and the adversary's output in the real execution be indistinguishable from that pair in the ideal execution.

Security with Aborts

Fairness and guaranteed output delivery are frequently unattainable (§5), so the definition is then relaxed and kept. In the ideal world with aborts the corrupted party may send $\bot$ instead of an input, and may also, after receiving its own output and before the honest party receives anything, instruct the trusted party to abort. Privacy, correctness and independence of inputs survive; fairness does not. Almost every practical two-party protocol achieves this notion.

Composition

Sequential composition is proved through the hybrid model: each subprotocol is replaced by its ideal functionality, so a proof may treat oblivious transfer or a commitment as a trusted box and reason only about the surrounding messages. Every composed proof in this chapter is of that form. Universal composability strengthens the quantifier so that security holds in the presence of arbitrary concurrent protocols.

The smallest non-trivial functionality has no inputs: output a uniform bit $y$ that neither party can bias. The obvious protocol is for Alice to pick $b_1 \getsr \bits$, Bob to pick $b_2 \getsr \bits$, both to publish and both to output $y = b_1 \oplus b_2$. If either bit is uniform and independent of the other, the XOR is uniform. Messages arrive in some order, and whoever speaks second sees $b_1$ and chooses $b_2 = b_1 \oplus y^\ast$ to force any $y^\ast$ it likes; the Internet offers no simultaneous transmission.

A commitment scheme supplies the missing simultaneity. The protocol runs:

Bob chooses $b_2$ blind, and Alice is bound to the $b_1$ she fixed before seeing $b_2$. Against malicious parties, hiding protects Bob's ignorance before step 2 and binding stops Alice from changing $b_1$ after it. The guarantee has one hole. It is the subject of §5: nothing forces Alice to send step 3 at all.

The construction used in the course models a hash function $\Hash$ (SHA-256, say) as a random oracle. To commit to $b$, pick $r \getsr \bits^{\lambda}$ and output $\Hash(b \,\|\, r)$; to open, send $(b, r)$. Hiding holds because a random oracle's output on an unqueried point is uniform, so the commitment is a uniform string independent of $b$ except with negligible probability that the adversary guesses $r$. Binding holds because a valid double opening is a collision $\Hash(0 \,\|\, r_0) = \Hash(1 \,\|\, r_1)$ on distinct points, and collisions in a random oracle require roughly $2^{\lambda/2}$ queries. The randomness $r$ is essential, since $\Hash(b)$ alone is trivially invertible over a two-element message space; collision resistance is developed in Chapter 1.

Coin tossing with commitments is also where the chapter's first genuine impossibility appears. It recurs throughout: Alice can refuse to open. She sees $b_2$, computes the outcome and stops if she does not like it. Bob learns nothing about $b_1$, so he cannot compute $y$ either; privacy survives, fairness does not. The next section is about that.

Two distinct things go wrong in the commitment-based coin toss.

Problem 1: fairness. Alice can abort after seeing $b_2$. The abort is inherent to the setting: in a two-party protocol somebody receives the last message, and whoever is one message ahead can stop. Cleve's theorem makes the impossibility quantitative: in any $r$-round two-party coin-tossing protocol one of the parties can bias the outcome by $\Omega(1/r)$, so a perfectly fair coin toss between two parties is impossible however many rounds are used. The standard achievable notion for two parties is therefore security with aborts (§3); fairness and guaranteed output delivery are reserved for the honest-majority setting of §12.

Problem 2: enforcement. A perfectly fair protocol only produces a number. Nothing in it makes the loser of a bet pay; the trusted party computes without enforcing.

Both problems accept a monetary attack. The mechanism is a deposit forfeited on abort, implemented with the Bitcoin scripting language of Chapter 6. A hash-locked transaction with $Y = \Hash(X)$ can be redeemed only by a spender who publishes $X$; here $X = (b_1, r)$ is the opening of Alice's commitment.

• Alice posts a commit transaction worth 1 BTC, spendable either by Alice's signature together with $(b_1, r)$ such that $Y = \Hash(b_1, r)$, or by Alice's and Bob's signatures jointly.
• Before posting, Alice hands Bob a signed refund transaction that spends commit to Bob after a one-day timelock.
• If Alice opens the commitment within the day she redeems her own deposit and the coin toss completes. If she does not, Bob posts refund and takes the 1 BTC.

The abort remains possible; the mechanism puts a price on it. The same stake can be made to move according to the computed result. In Ethereum (Chapter 7) the same logic is a short contract with three entry points: commit, which stores the hash, sets a timeout and accepts the deposit; open, which checks the opening and releases the deposit; refund, which after the timeout returns the funds to the counterparty.

The general result is that any two-party stateless functionality can be realized this way with financial consequences attached. The construction extends to multiparty reactive functionalities. A worked application is selling secret information: the parties compute the union of their sets, with each newly learned element triggering a payment.

Identification by signature works and leaks. If the verifier sends a random message $m$ and the prover returns $\sigma = \mathbf{S}(sk, m)$, the verifier walks away with a transferable proof that the prover was there: the protocol is not deniable, since the signature convinces third parties who were never part of the exchange. The question is whether a verifier can be convinced while learning nothing it could not have produced alone.

The Schnorr Protocol

Let $\mathbb{G}$ be a cyclic group of prime order $q$ with generator $g$, and let $x = g^w$. The prover knows $w$; the verifier holds $x$. The messages are:

Completeness is a one-line computation: $g^{\beta w + a} = g^{a} \cdot (g^{w})^{\beta} = \alpha \cdot x^{\beta}$. Honest-verifier zero knowledge follows by simulating backwards: pick $\beta, \gamma \getsr \Zq$ and set $\alpha = g^{\gamma} \cdot x^{-\beta}$, which has exactly the real distribution. For soundness, note that every group element is a power of $g$, so the language is trivial and plain soundness is vacuous; the meaningful statement is knowledge soundness. Two accepting transcripts $(\alpha,\beta,\gamma)$ and $(\alpha,\beta',\gamma')$ with $\beta \ne \beta'$ yield $w = (\gamma - \gamma')(\beta - \beta')^{-1} \bmod q$, so a prover that succeeds on two challenges knows the discrete logarithm. The precise notion is a proof of knowledge.

Everything in NP

Assuming one-way functions exist, every language in NP has a zero-knowledge proof, obtained by giving one for an NP-complete language such as graph 3-coloring or Hamiltonicity and reducing.

A Construction from Homomorphic Encryption

The course also derives a protocol from Fully Homomorphic Encryption (FHE) (Chapter 4). Alice generates $(pk, sk)$, encrypts the witness as $\vec{c} \getsr \Enc(pk, w)$ and sends $(pk, \vec{c})$. Bob evaluates $f_{x,R}(w) = R(x,w)$ homomorphically, returning $c'$; Alice decrypts and sends $d = \Dec(sk, c')$; Bob accepts if $d = 1$. This is unsound as stated, because Alice performs the decryption and can send $d = 1$. Soundness is added by a coin flip: Bob picks $\beta \getsr \bits$ and returns either the real evaluation (if $\beta = 1$) or a fresh encryption of $0$ (if $\beta = 0$), then checks $d = \beta$. For $x \notin L$ the honest evaluation also encrypts $0$, so the two cases are indistinguishable to Alice and she cheats with probability at most $1/2$; repetition drives that down. Well-formedness of $pk$ and $\vec{c}$ is forced by openings: Alice generates two key pairs and Bob asks her to open one at random, and Alice encrypts shares $w_1 \oplus w_2 = w$ under the other, one of which Bob asks her to open. Last, the protocol so far is only honest-verifier zero knowledge, since a malicious Bob can return the first component of $\vec{c}$ itself, making $d$ the first bit of $w$. Commitments repair it: Alice commits to $d$, Bob reveals the randomness proving he evaluated as prescribed and only then does Alice open.

Fiat-Shamir

A three-move public-coin proof becomes non-interactive by computing the challenge as $\beta = \Hash(x, \alpha)$, so the proof is the single message $\zeta = (\alpha, \gamma)$. Security is in the random oracle model. Applications include revealing $m_2$ from a signed $m = m_1 \| m_2$ while keeping $m_1$ and the signature secret, and proving from a signed identity card that one is over 18 without revealing a date of birth. In this chapter the application is the GMW (Goldreich, Micali and Wigderson) compiler of §12, where each party proves in zero knowledge that its messages were computed correctly.

All of the above still leaves the central two-party difficulty untouched: Bob must obtain something that depends on his own secret choice, from a sender who must not learn what he chose. That primitive is oblivious transfer.

Why One Call Already Does Secure Computation

Set $(s_0, s_1) = (0, b')$ where $b'$ is the sender's private bit. The receiver's output is $s_b$, which is $1$ exactly when $b = b' = 1$: a single Oblivious Transfer (OT) computes the AND of two private bits, revealing nothing else. AND with negation generates every Boolean function, and OT is used once per gate, so OT is complete for secure computation; §8 and §9 make that concrete.

Why It Cannot Be Done with Information-Theoretic Security

The course proves that AND (and hence OT) is impossible to compute with unconditional security, even against passive adversaries. Say a transcript $T$ is consistent with $x_1$ if there exist $r_1$ and $(x_2, r_2)$ making $T$ the transcript of an honest execution on inputs $(x_1, r_1)$ and $(x_2, r_2)$. Consider an execution with $x_1 = 0$.

• If $x_2 = 0$, the output is $0$ in both cases $x_1 \in \bits$, so $T$ must also be consistent with $x_1 = 1$; otherwise Bob, who sees $T$, would learn $x_1$, violating privacy.
• If $x_2 = 1$, then $T$ cannot be consistent with $x_1 = 1$, because the prescribed output differs between $(0,1)$ and $(1,1)$ and correctness pins it down.

An unbounded Bob holding $x_2$ and $T$ simply tests whether $T$ is consistent with $x_1 = 1$: if it is, $x_2$ was $0$; if not, $x_2$ was $1$, and symmetrically he recovers $x_1$. The test is a search over all $r_1$, which is why the argument does not contradict computational security. Every secure protocol for AND must therefore rest on a computational assumption.

OT with Passive Security, from ElGamal

An ElGamal ciphertext under public key $h = g^{x}$ is $c = \big(g^{r},\, h^{r} \cdot m\big)$ (Chapter 2). A public key can be sampled obliviously: a uniform group element is a valid key whose secret key nobody knows. The transcript is:

Receiver privacy is perfect: $h_0$ and $h_1$ are both uniform, so the sender's view is independent of $b$. Sender privacy holds under the Decisional Diffie-Hellman (DDH) assumption, since $c_{1-b}$ is an ElGamal encryption under a key whose secret key nobody holds. The adversary is semi-honest; a malicious receiver could pick both keys knowing both discrete logarithms and decrypt both ciphertexts, which is the gap the next construction closes.

OT with Active Security, from Suitable Public-Key and Symmetric-Key Encryption

Let $(\mathbf{K}, \Enc, \Dec)$ be a public-key scheme and $(\Enc', \Dec')$ a symmetric one. The sender generates the keys, so the receiver never gets to cheat at key generation. The transcript is:

The receiver cannot obtain $s_{1-b}$, because it does not know $k_{1-b}$; the sender cannot tell which of $k_0, k_1$ is the receiver's key, so $b$ stays hidden. Nothing has to be assumed about the receiver's honesty in generating keys, because the receiver generates none. That is the gap the ElGamal protocol leaves open. The adversary here is malicious.

Strings, and How to Get Millions of OTs

If the sender's inputs are vectors $s_i = (s_i^1, \dots, s_i^m)$, the passive case runs basic OT on each pair $(s_0^j, s_1^j)$ with the same choice bit $b$; the active case needs more care, and generic constructions exist. The optimization that matters at scale is OT extension: it turns $\lambda$ base OTs into polynomially many using only symmetric-key operations, which is what makes garbled-circuit protocols with millions of input bits feasible; the base OTs cannot be avoided, since OT provably cannot be built from symmetric primitives alone.

Oblivious Transfer (OT) computes one AND gate. A function is many gates, and running an interactive subprotocol per gate over a circuit with millions of gates is the cost to avoid. Yao's protocol sends the whole encrypted circuit in one shot and uses OT only for the evaluator's input bits.

Represent $f$ as a Boolean circuit, whose size is its number of gates. A single gate type suffices, since NAND is complete; the construction works verbatim for any gate with a two-by-two truth table. Alice, the garbler, encrypts the circuit together with her input and sends it. Bob, the evaluator, adds his own input and evaluates the encrypted circuit gate by gate. Everything on the internal wires stays hidden; only the output wires may be readable.

Common mistake. Garbling does not encrypt the parties' data as homomorphic encryption does. It garbles the computation itself. Each input bit becomes a random wire label; the evaluator walks the circuit using ordinary symmetric-key decryption at every gate.

Step 1: Wire Labels

For every wire $w$, input and internal wires alike, Alice picks two independent random keys $k_w^0, k_w^1 \getsr \bits^{\lambda}$, one per possible bit. These are not sent to Bob. A wire's semantics (which label means $0$) is known only to Alice.

Step 2: Double Encryption

A garbled gate must release a value only to someone holding two keys, so encrypt twice: $\Enc(k_1, \Enc(k_2, m))$. The construction needs two properties beyond ordinary security, because the evaluator will decrypt with wrong keys on purpose and must be able to tell.

• Elusive range. Without $k$ it is hard to produce a valid ciphertext under $k$.
• Verifiable range. Given $k$ and $c$ it is easy to test whether $c$ lies in the range of $\Enc(k, \cdot)$.

Both are supplied by a Pseudorandom Function (PRF) $\PRF$ mapping $n$ bits to $2n$ bits: to encrypt $x \in \bits^{n}$ under $k$, pick $r \getsr \bits^{n}$ and output

Decryption XORs $\PRF(k,r)$ back and checks that the last $n$ bits are zero. Verifiable range is that check; elusive range holds because predicting the last $n$ bits of $\PRF(k, r)$ without $k$ is infeasible. The padding block is the tag that tells the evaluator which row worked.

Step 3: The Garbled Table

For a gate with input wires $x, y$ and output wire $z$, computing $z = x \barwedge y$, Alice writes the truth table and encrypts each row's output label under the two input labels of that row.

Holding $k_x^{a}$ and $k_y^{b}$, exactly one row decrypts successfully, the row for $(a,b)$, and it yields $k_z^{a \barwedge b}$. The other three fail the range check. For an output gate the same table is built with the plaintext bits $0$ and $1$ in place of the output labels, which is how Bob eventually receives a plaintext bit in place of another opaque key.

Step 4: Permute

The four ciphertexts are sent in random order. Without this the row index would reveal the input bits: Bob would see that the third row decrypted and read off $(1,0)$. After permutation he holds four ciphertexts $c_1, \dots, c_4$ per gate, learns which one decrypted and learns nothing from that fact.

A Worked Gate, with Numbers

The lab below garbles $f(x_1, x_2) = x_1 \wedge \neg x_2$ with 16-bit labels and a deterministic mixer standing in for $\PRF$. In its default state the wire labels are $k_x^0 = \texttt{2e5d}$, $k_x^1 = \texttt{886f}$ on Alice's wire, $k_y^0 = \texttt{e5bb}$, $k_y^1 = \texttt{e86e}$ on Bob's and $k_z^0 = \texttt{8b8f}$, $k_z^1 = \texttt{6e97}$ on the output wire. The garbled table in transmission order:

Take inputs $x_1 = 1$, $x_2 = 0$. Alice sends her label $k_x^1 = \texttt{886f}$; Bob obtains $k_y^0 = \texttt{e5bb}$ by one OT. He tries all four ciphertexts against the pair: $c_1$, $c_3$ and $c_4$ fail the range check, and $c_2$ decrypts to $k_z^1 = \texttt{6e97}$. The output gate publishes the decoding $\texttt{8b8f} \mapsto 0$, $\texttt{6e97} \mapsto 1$, so Bob reads output $1$: Alice is richer on one bit. At an internal gate no decoding is ever published, and Bob is left holding one opaque label.

The tables alone are useless: Bob cannot start without one label per input wire, since the input wires belong to two different people. That asymmetry is where Oblivious Transfer (OT) enters. The full message flow, for Alice's input bits $\alpha_1, \dots, \alpha_n$ and Bob's input bits $b_1, \dots, b_m$:

A label is a uniform string, so step 2 reveals nothing: Bob has no way to associate it with a bit. The permutation of the tables means the position at which a row succeeds tells him nothing either. Step 3 is forced: Bob cannot reveal his bits, and Alice cannot send both labels for a wire, because with both Bob could evaluate $f$ at several inputs, learning $f(\vec{\alpha}, \cdot)$ on points he never held. During evaluation, at each gate Bob tries the four ciphertexts with his two labels, exactly one passes the range check and he obtains one label on the output wire. He never learns which bit any internal label represents. Alice, who receives nothing after the OTs, learns nothing at all.

Common mistake. Bob does learn something: the output. That is the point. The guarantee is that nothing beyond the output leaks; the circuit's shape and size stay public throughout.

Generalizations the Slides Supply

Randomized functionalities. To compute $f(x_1,x_2; r)$ for random $r$, define the deterministic $g\big((x_1, r_1), (x_2, r_2)\big) = f(x_1, x_2; r_1 \oplus r_2)$, let each party contribute its own half and run a protocol for $g$. If either party is honest its half is uniform, so $r$ is uniform. This works in the passive and the active setting.

Two outputs, semi-honest. Given a protocol delivering one output, put $f_1$ and $f_2$ behind one-time pads. Alice picks $r_1$, Bob picks $r_2$ and they evaluate

Bob receives $u \| v$, forwards $u$ to Alice and outputs $v \oplus r_2$; Alice outputs $u \oplus r_1$. Each party's share of the output is masked by a pad only the other party lacks.

Two outputs, malicious. The construction above lets a malicious Bob send a wrong $u$, so a one-time Message Authentication Code (MAC) is added. Alice picks $r_1$ and MAC keys $\alpha, \beta$. The parties evaluate a one-output function returning $c_1 \| f_2(x_1,x_2) \| \gamma$ where $c_1 = f_1(x_1,x_2) \oplus r_1$ and $\gamma = \alpha \cdot c_1 + \beta$ over a finite field. Bob obtains $u \| v \| w$, forwards $u \| w$ and outputs $v$; Alice outputs $u \oplus r_1$ only if $w = \alpha u + \beta$. Since $\alpha, \beta$ are unknown to Bob, a forged $u$ passes with probability $1/\abs{\mathbb{F}}$.

The Cost, Historically

Optimizations Beyond the Slides

Two standard ones explain why garbled circuits are fast today. Point-and-permute attaches a random select bit to each label, arranged so that the two select bits held by the evaluator index the one row he must decrypt: one decryption per gate instead of four, with the permutation still hiding the semantics. Free XOR fixes a global offset $\Delta$ and sets $k_w^1 = k_w^0 \oplus \Delta$ for every wire, so an XOR gate needs no ciphertexts at all (the output label is the XOR of the input labels), at the price of a stronger assumption on the hash function.

Worked number. The Advanced Encryption Standard (AES) circuit for one block has about 6800 AND gates. At two 128-bit ciphertexts per AND gate (half-gates) with free XOR, a garbled AES-128 costs about 218 kilobytes.

Nothing in Yao's protocol forces Alice to garble the circuit she claims. She can garble a circuit for a different function that leaks Bob's input, or plant one bad gate whose behavior depends on a wire she cares about; Bob decrypts opaque strings and cannot tell. Two further gaps appear at the same time: Alice may cheat in the Oblivious Transfers (OTs), and, once the protocol acquires more rounds, she may use inconsistent inputs across them.

Cut-and-Choose

Alice sends $k$ independently garbled copies of the circuit. Bob picks a random challenge set of $t$ of them and asks for those to be opened completely (all labels and randomness) and checks each is a correct garbling of $f$, aborting if not. The remaining $\ell = k - t$ circuits are evaluated. With $t = k/2$ and $k = 80$ circuits, a garbler who corrupts one circuit escapes detection with probability $1/2$, and one who corrupts $40$ circuits is caught except with probability $2^{-40}$.

What to Do with the Evaluated Copies

First idea: abort on disagreement. Bob evaluates all $\ell$ unopened circuits and aborts if the outputs differ. This is insecure. Alice corrupts a few circuits so that they compute $f$ when $b_1 = 1$ and $f + 1$ when $b_1 = 0$. If $b_1 = 1$ all outputs agree and Bob proceeds; if $b_1 = 0$ he aborts with noticeable probability. Whether Bob aborts is therefore a function of his private input, and no simulator, which does not know $b_1$, can reproduce that behavior.

Second idea: majority. Bob outputs the majority of the $\ell$ results. A constant number of corrupted circuits changes nothing, since flipping the majority takes more than $\ell/2$ of them, and corrupting that many is caught by the challenge except with negligible probability.

Input Consistency

Majority forces a reordering of the messages, which creates a new gap. Alice cannot send the labels for her own input together with the circuits, because opening a challenged circuit would then reveal, in the clear, which of the two labels she chose for each of her wires. Those choices are her input. So she sends her input labels after the challenge is answered, one set per evaluated circuit: $k_{\vec{a}}^{1}, \dots, k_{\vec{a}}^{\ell}$. Nothing ties those $\ell$ label sets to the same input.

The attack is concrete. Let $f(A, B) = \bigoplus_i a_i \cdot b_i$ and suppose Bob takes the majority of four evaluations. Alice feeds $A = 0001$ to the first circuit, $0010$ to the second, $0100$ to the third and $1000$ to the fourth. Each evaluation returns a single bit $b_i$ of Bob's input. The majority of those bits is the protocol output. Alice has, however, learned four bits of $B$ that no single evaluation of $f$ would ever have revealed. The fix is to have Alice commit to her input labels up front and prove in zero knowledge, twice, that the committed labels are consistent across all evaluated circuits ($\pi_1$ with the circuits, $\pi_2$ with the revealed labels).

Malicious OT and Selective Failure

The OT subprotocol must itself be secure against malicious adversaries, so the passively secure ElGamal variant of §7 will not do. Even a maliciously secure OT is not the end of it. In the selective failure attack Alice submits, for one of Bob's input wires, the correct label vector $\{k_{j,i}^{0}\}$ in the $b_j = 0$ slot and bogus keys in the $b_j = 1$ slot. If Bob's bit is $0$ everything works; if it is $1$ evaluation fails and he aborts. Whether the protocol completes is again a function of a single bit of Bob's private input, so that bit leaks. The remedy is OT on committed inputs, with a zero-knowledge proof ($\pi_1^{\mathsf{OT}}$, $\pi_2^{\mathsf{OT}}$) that the labels offered in the OTs are the ones committed to and used in the circuits.

What went wrong. Lindell and Pinkas (2007) named the selective failure attack: a malicious garbler ties aborts to the evaluator's input bits. The lesson reaches beyond oblivious transfer: a malicious-secure protocol must make its abort decision independent of the honest input.

The assembled protocol runs:

1. OT on committed inputs, with a proof that the offered labels are the committed ones.
2. $k$ garbled circuits, with consistency proofs.
3. A challenge set of size $t$, opened and checked.
4. The answer to the challenge, Alice's input labels for the unopened circuits and a second proof.
5. Majority output over the evaluated circuits.

Garbled circuits are two-party and constant-round. The $n$-party route is different: keep every intermediate value split among the parties so that no admissible coalition can read it, and compute on the pieces. That requires a sharing primitive with an exact threshold.

The case $t = n-1$ (every party is needed) has a one-line solution. To share $m \in \bits^{\lambda}$, pick $s_2, \dots, s_n \getsr \bits^{\lambda}$ and set $s_1 = m \oplus s_2 \oplus \dots \oplus s_n$; then $m = s_1 \oplus \dots \oplus s_n$, and any $n-1$ shares are uniform and independent of $m$, exactly as in the one-time pad. This is additive sharing, and over a field $\mathbb{F}$ one writes it with $+$ instead of $\oplus$. It gives no intermediate threshold.

Worked number. Modulo 211, split the salary 30 into shares 40, 60 and 141, since $40 + 60 + 141 = 241 \equiv 30 \pmod{211}$. Any two shares alone are uniform noise; all three rebuild the secret.

The Integer Version Leaks

Try the polynomial idea over the integers before seeing why the field is needed. Let $t = 1$ and $n = 2$, share $m = 9$ by picking $a = 5$ and setting $p(X) = 9 + 5X$, and give $P_2$ the share $s_2 = p(2) = 19$. One share was supposed to reveal nothing, but $s_2 = m + 2a$ and $2a$ is even, so $s_2$ has the parity of $m$, so the eavesdropper reads off that the secret is odd. The share rules out half of all candidates outright, since $s_2 - m'$ must be even and non-negative.

Re-run the same numbers over the field $\mathbb{F}_{17}$: $p(X) = 9 + 5X$ with all arithmetic modulo $17$, so $s_2 = p(2) = 19 \bmod 17 = 2$. For every candidate $m' \in \mathbb{F}_{17}$ there is exactly one coefficient $a' = (2 - m') \cdot 2^{-1} \bmod 17$ with $m' + 2a' = 2$, so every candidate is equally consistent with the share. Parity is not a property of field elements, so the attack dies. The privacy proof below is this calculation for general $t$.

Shamir's Scheme

Shamir's construction gets every threshold from the fact that a polynomial of degree at most $t$ is determined by $t+1$ points and undetermined by $t$.

Worked Reconstruction

Re-run the opening example with $t = 1$, $n = 2$ over $\mathbb{F}_{17}$: the polynomial is $p(X) = 9 + 5X$. The shares are

Pooling both shares, the Lagrange coefficients at $0$ are $p_1(0) = \frac{2}{2-1} = 2$ and $p_2(0) = \frac{1}{1-2} = -1$, so

the secret $p(0)$ from the polynomial the shares came from. Any single share, as the opening example showed, is consistent with every $m \in \mathbb{F}_{17}$.

Linearity

Shamir shares add. If $p$ and $q$ are degree-$\le t$ polynomials sharing $m$ and $m'$, then $p + q$ has degree at most $t$ and $(p+q)(0) = m + m'$, so the shares $p(i) + q(i)$, computed locally with no communication, share $m + m'$. The same holds for multiplication by a public constant $c$: the shares $c \cdot p(i)$ share $c \cdot m$. Additive sharing has the same property. This is the algebraic fact that makes the protocol of §12 possible. Its failure for products is what makes that protocol interactive.

Variants Named in the Course

• Computational secret sharing: relaxes privacy to computational, buying shorter shares.
• General access structures: the authorized sets need not be "all sets of size $> t$"; any monotone family can be realized.
• Verifiable secret sharing: lets the parties detect a malicious dealer distributing inconsistent shares.
• Robust and non-malleable secret sharing: handles malicious players submitting wrong shares at reconstruction time.

Threshold Cryptography

Secret sharing is useful on its own. A signing key $sk$ that must not sit on any one machine is shared among $n$ machines, which sign in a distributed manner by running a Multiparty Computation (MPC) protocol for the signing function, so that $sk$ is never reconstructed anywhere. This is standard practice for cryptocurrency wallets and certificate authorities. It returns in §13 as the way a redaction trapdoor is held.

With $n$ parties the two-party impossibilities loosen. If a majority is honest, a protocol can compute any functionality with fairness and guaranteed output delivery and, given private channels, with no computational assumption at all. The thresholds of this section are $t < n/2$ for passive security and $t < n/3$ for active security. The protocol below is the BGW/GMW line of work (BGW: Ben-Or, Goldwasser and Wigderson; GMW: Goldreich, Micali and Wigderson), stated for a passive threshold adversary corrupting $t < n/2$ parties.

Represent the function as an arithmetic circuit over $\mathbb{F}$, built from addition gates, multiplication gates and multiplication by public constants. The invariant maintained throughout is that every wire value is Shamir-shared among the parties with threshold $t$. Write $[u]$ for a sharing of $u$.

Step 1: Share the Inputs

Each party shares its own input $u$ by picking a random polynomial $p$ of degree at most $t$ with $p(0) = u$ and sending $p(i)$ to $P_i$. At the end of this phase every party holds one share of every input. No coalition of $t$ parties knows any input but its own.

Step 2a: Addition and Public Constants, for Free

Given $[u] = (u_1,\dots,u_n)$ and $[v] = (v_1,\dots,v_n)$, each party locally computes $w_i = u_i + v_i$. By linearity, $w_i = (p+q)(i)$ where $p + q$ has degree at most $t$ and $(p+q)(0) = u + v$, so $(w_1,\dots,w_n)$ is a threshold-$t$ sharing of $u+v$. No messages are sent. Likewise $w_i = c \cdot u_i$ shares $c \cdot u$.

Step 2b: Multiplication, and Why It Costs a Round

Local multiplication almost works and then fails in one specific way. Each party computes $z_i = u_i \cdot v_i = (p \cdot q)(i)$. The polynomial $p \cdot q$ satisfies $(p \cdot q)(0) = u v$, so the product is still encoded, although its degree is $2t$. With $n > 2t$ that is still reconstructable from all $n$ shares, so one multiplication is survivable. Two are not: the degree becomes $4t$. It doubles again at every level of the circuit. The invariant must be restored.

The degree reduction uses the linearity of reconstruction. Let $\alpha_1, \dots, \alpha_n$ be the Lagrange coefficients for recovering the value at $0$ of a degree-$2t$ polynomial from its $n$ points, so that $uv = \sum_i \alpha_i z_i$. Each party $P_i$ picks a fresh random polynomial $p_i$ of degree at most $t$ with $p_i(0) = z_i$ and sends $z_{i,j} = p_i(j)$ to $P_j$; that is, it re-shares its own product share. Each $P_j$ then computes

The polynomial $p^{*}$ is a linear combination of degree-$\le t$ polynomials, hence of degree at most $t$, and

So $(w_1, \dots, w_n)$ is a threshold-$t$ sharing of the product, so the invariant holds again. The cost is one round of communication per multiplication layer; the circuit's multiplicative depth, not its size, sets the round complexity.

Step 3: Reconstruct the Output

Each party broadcasts its share of each output wire, and everyone interpolates. Because the adversary is a minority and each wire is shared with threshold $t < n/2$, the honest parties always hold enough shares: output delivery is guaranteed, and fairness comes with it.

From Passive to Active

The GMW compiler upgrades any passively secure protocol: every party runs the semi-honest protocol and, alongside each message, proves in zero knowledge (§6) that the message was computed correctly from its committed input and randomness. A malicious party is thereby reduced to a semi-honest one: it may still choose its input, which the ideal world permits. It may also abort, which is why the honest majority restores fairness. The actively secure version of the BGW line is where the stricter bound $t < n/3$ applies. The compiler is a feasibility result; efficient maliciously secure MPC is a separate literature.

Beaver Triples, and Where Homomorphic Encryption Enters

A Beaver triple is a triple of sharings $[a]$, $[b]$, $[c]$ with $c = ab$, prepared before the inputs are known. The efficient protocols that drop the honest majority (SPDZ, the protocol of Damgård, Pastro, Smart and Zakarias, plus its descendants) multiply with one. To multiply $[u]$ and $[v]$, the parties open $d = u - a$ and $e = v - b$ and locally compute $[uv] = [c] + e[a] + d[b] + de$, one round of openings per multiplication layer. Generating the triples is the offline problem, and SPDZ solves it with somewhat homomorphic encryption, the Chapter 4 primitive that evaluates circuits on encrypted data. MP-SPDZ implements this family of protocols.

Worked number. Work modulo 101 with $a = 4$, $b = 7$ and $c = 28$. To multiply shared $x = 9$ and $y = 5$, the parties open $d = 5$ and $e = 99$; their shares rebuild $28 + 35 - 8 - 10 = 45$, indeed $9 \cdot 5$.

Blockchains are proposed for healthcare records, identity and reputation management, IoT device registries, smart grids, supply chains and post-trade settlement of US cash equities. All of these presuppose something Bitcoin explicitly refuses: the ability to correct the record. The immutability of Chapter 6 is not always a feature.

The need is concrete. Hard forks already repair human error. The Decentralized Autonomous Organization (DAO) fork reversed a $60 million theft on Ethereum (Chapter 7). The GDPR (General Data Protection Regulation) right to be forgotten conflicts with an append-only ledger. A case stalled after a Dutch man's identity information was found on the Bitcoin chain; fines reach 4% of annual revenue or €20 million. The Open Data Institute notes that immutable storage "may be incompatible with legislation which requires changes to the official truth" and that metadata alone can be revealing even when personal data stays off-chain. The European Union Agency for Cybersecurity (ENISA) asks for standard methods for removing data from a ledger, and ESMA observes that immutability is ill-suited to securities markets where operational errors may require cancelling a transaction.

The goal is to retain ordinary blockchain validation while adding a controlled procedure for editing or removing a block. Editing block $B_1$ to $B_1'$ breaks the hash pointer held by $B_2$, and so does removing it. Repairing that pointer means producing a hash collision on demand, which is what a chameleon hash provides.

Chameleon Hashing

A chameleon hash function $\Hash(\cdot;\cdot)$ takes a message and a randomness, is collision resistant to anyone holding only the public hash key $hk$ and admits efficient collision finding for anyone holding the trapdoor $tk$: given $(m, r)$ and any $m'$, one computes $r'$ with $\Hash(m; r) = \Hash(m'; r')$.

The fix is a stronger notion. Enhanced collision resistance requires that finding a collision remain hard even for an adversary with access to a collision oracle: the adversary may request collisions on messages of its choice and still cannot produce a fresh one, and in particular cannot extract $tk$. The randomness then acts as a check value: a redaction is authorized by knowing the $r'$ that makes the block hash to its old digest. Constructions satisfying this notion are what the redactable blockchain is built from.

A redaction leaves a visible trace. The repaired link shows that it was recomputed, while a removed block leaves a marker in its place. The chain records that a change occurred without retaining the removed content.

Who Holds the Trapdoor

The design reuses the chapter's own primitives. The trapdoor is a key of the same criticality as a certificate authority's, so no single party holds it: it is secret-shared among the authorities (§11), none of whom knows $tk$, and when a redaction is approved the collision is computed by a secure distributed protocol (§12). The design is aimed at permissioned systems: the chain stays decentralized and immutable in the ordinary sense, while a quorum of administrators under agreed governance can edit, rewrite or remove blocks. Two objections are answered in advance: appending an amendment is usually pointless, since the harmful data remains; and storing only a hash does not help, because a hash still proves existence.

The Permissionless Variant

A trapdoor held by administrators is a non-starter for an open cryptocurrency. The permissionless variant gives a redaction procedure with no additional trust assumption, decided by consensus, publicly verifiable and accountable.

• Block structure. Each block carries two links instead of one: the old link and the new link.
• Request. A proposer publishes a candidate redacted block $B_1'$ and its hash $h$ to a candidate pool.
• Voting. Miners who retrieve the candidate vote by including $h$ in blocks they mint. The voting phase spans an epoch: 1024 blocks in Bitcoin, roughly two weeks. A policy such as "approved if 50% of the blocks in the epoch voted for it" decides the outcome.
• Validation. A standard block is checked as usual, plus the validity of both links. A redacted block is checked for proof of work with respect to the old link, for the new link being broken and the old link intact and for the redaction having been approved.

In the Bitcoin integration the old link is $\Hash(\mathit{prev\_hash}, TX, TY, \mathit{salt})$, where $TY$ comes from the previous block header. The new link is $\Hash(\mathit{prev\_hash}, TX', TY, \mathit{salt})$ with $TX'$ the redacted transaction root. A redacted transaction is replaced by its own hash inside the Merkle tree of Chapter 6, so the rest of the tree and every proof of inclusion for an untouched transaction still verify.

• Secure Multiparty Computation, Yehuda Lindell. The standard gentle survey for a general CS audience.
• Wikipedia: Secure multi-party computation. The millionaires problem, the real/ideal framework, the adversary taxonomy, thresholds and real deployments.
• Wikipedia: Shamir's secret sharing. A worked example and the integer-arithmetic leak fixed by a finite field.
• Wikipedia: Garbled circuit. The gate-by-gate protocol, where oblivious transfer fits, free XOR and cut-and-choose.
• Wikipedia: Oblivious transfer. Rabin and 1-out-of-2 OT, including the result that OT suffices for all of MPC.
• MP-SPDZ. A reference teaching framework with a protocol matrix across security models and technologies.
• Wikipedia: Homomorphic encryption. The taxonomy, Paillier additivity, the FHE history and libraries.

Further reading: Shai Halevi (2017), Homomorphic Encryption, Chapter 5 of Tutorials on the Foundations of Cryptography, Yehuda Lindell ed., Springer, which develops the primitive that §12 uses to generate multiplication triples.