Yao's protocol for semi-honest and malicious adversaries.

Lecture 21 set up the problem and the definition. Mutually distrustful parties evaluate a function on secret inputs; security is defined by comparison with an ideal world in which an incorruptible trusted party collects the inputs and returns the outputs. A protocol is secure when every real adversary has a simulator producing an indistinguishable ideal-world execution. The properties one would have enumerated (privacy, correctness, independence of inputs, fairness) follow. Fairness is unattainable for two parties, so the achievable notion is security with aborts. Two primitives were built: commitments, which buy the simultaneity that unbiasable coin tossing needs, and 1-out-of-2 oblivious transfer, which hides the receiver's choice from the sender and the unchosen message from the receiver. One OT call already computes a private AND, and AND cannot be computed with unconditional security, so OT is where computational assumptions enter.

Oblivious transfer computes one gate. A function is a circuit of millions of gates, and running an interactive subprotocol at each one is what this lecture avoids. Yao's idea is to encrypt the entire circuit once and send it. Each wire is assigned two random labels, one per possible bit; each gate becomes its truth table with the output label encrypted under both input labels; padding makes a wrong row recognizably wrong; and the four rows are shuffled so that the position of the row that works reveals nothing. The garbler sends the tables together with the labels for its own input bits, which are uniform strings and therefore harmless. The evaluator obtains one label per its own input wire by oblivious transfer. Evaluation then walks up the circuit decrypting exactly one row per gate. The security argument rests on one property: the evaluator ends with one label per wire and never learns which bit that label denotes, except at the output gates where the decoding is deliberately published.

The second half asks what a malicious garbler can do. The answer is "garble a different circuit". Cut-and-choose is the response: send $k$ copies, open a random half, check them. The balls-and-bins calculation shows the procedure caps cheating at a constant number of circuits and does not eliminate it. Aborting on disagreement leaks, because whether the evaluator aborts depends on its own private input; taking the majority fixes that but forces the garbler's input labels to be sent later, opening an input-consistency attack that recovers several bits of the evaluator's input at once. Committed inputs with zero-knowledge proofs close it. The same treatment is needed inside the OTs, where the selective failure attack makes completion of the protocol depend on a single bit of the evaluator's input. Four repairs, each one forced.

1. Garbling a circuit: wire labels, double encryption with elusive and verifiable ranges, the garbled table for a NAND gate, output gates and the permutation, plus a worked gate with the lab's own numbers. The main animation of the chapter is here; step through it to the end.
2. The garbled gate stepper: the lab in the same section garbles $f(x_1,x_2) = x_1 \wedge \neg x_2$, the one-bit millionaires' comparison, and shows which row survives the range check for each pair of inputs.
3. Yao's protocol, end to end: how each side gets its labels, why the garbler may send its own but not the evaluator's, the theorem and the generalizations to randomized and two-output functionalities. The historical performance table is here too.
4. Yao against malicious adversaries: cut-and-choose and its probability bound, the abort-on-disagreement attack, majority output, input consistency, malicious Oblivious Transfer (OT) and selective failure.

• Why must a garbled circuit never be evaluated twice? The exercise tests whether the label invariant was understood.
• Bound the probability that cut-and-choose misses a cheating garbler: the balls-and-bins computation, with the $2^{-c}$ bound derived in full.
• A protocol secure against semi-honest but not malicious adversaries: the gap this lecture spends its second half closing.
• Why Oblivious Transfer (OT) is complete: Yao's protocol is one of the two answers.