Introduction to multiparty computation. Coin tossing and oblivious transfer.

Lecture 20 finished the survey of alternative currencies on Chapter 7. Filecoin replaced proof of work with proofs of space and of replication, so the resource demonstrated is useful storage. It also created a market in which clients pay for storage, providers prove that they still hold the data and the chain records the agreements. Zerocash addressed Bitcoin's fully public ledger. Coins live in a shielded pool as commitments (digital envelopes whose contents stay hidden and cannot later be changed); spending publishes a nullifier that retires exactly one commitment without saying which, plus a zero-knowledge proof that the spender knew an opening to some unspent commitment of the right value. The proof establishes validity without identifying the spent commitment. This lecture turns that property into the definition of security for arbitrary computations.

Every protocol so far had a fixed goal: transfer value, agree on a chain, exchange a key. This lecture asks for an arbitrary goal. Millionaires who will not state numbers, a coin neither party can bias, an auction that hides the losing bids: all are the same problem, evaluating a function on secret inputs and revealing nothing but its output.

The security definition is the central step. Listing forbidden attacks gives a different list for auctions and elections, with no argument that either list is complete. The lecture replaces those lists with a comparison: an incorruptible trusted party collects the inputs and hands back the outputs. A protocol is secure when running it is indistinguishable from that interaction. A simulator proves the usual properties (privacy, correctness, independence of inputs, fairness, guaranteed output delivery) follow from the ideal world.

The lecture then builds the required primitives. Coin tossing by exchanging bits fails because whoever speaks second can adapt, so commitments (digital envelopes that hide a value until it is revealed) enforce simultaneity; and commitments immediately expose the limit of the approach, since the committer can refuse to open. Fairness is unachievable for two parties, so security with aborts (the attacker may abort the protocol, possibly after seeing the output) is the notion protocols actually meet. The lecture detours through Bitcoin-based deposits that make aborting expensive. Zero knowledge (proving a statement while revealing nothing beyond that it is true) appears both as an application and as the tool that later compels malicious parties to follow the protocol. The lecture closes on oblivious transfer, which hides a choice from the sender and the unchosen message from the receiver, already computes a private AND, provably cannot be built with information-theoretic security (security that holds even against unlimited computing power) and is therefore where computational assumptions enter multiparty computation.

1. The Multiparty Computation (MPC) problem: the millionaires' problem, secure dating, auctions and voting and why a trusted party would make all of them trivial.
2. What security has to mean: the five properties, then the adversary ladder (semi-honest: follows the protocol but tries to learn from the transcript; covert: may cheat but fears detection; malicious) and the $t < n/2$ and $t < n/3$ thresholds (at most $t$ corrupted parties out of $n$ in total) in one table, with the attacker's capability beside each. The playground lab here demonstrates the point: the output itself leaks. No protocol can stop it.
3. The real/ideal framework and simulation: the definitional core. The animation steps through the definition to the last beat; the simulator is the whole content of the definition. The final beat is the weakening to security with aborts.
4. Coin tossing and commitments: binding and hiding stated precisely, and the hash-based commitment in the random oracle model (which treats the hash function as an ideal random function).
5. Fairness, aborts and enforcement with money: Cleve's impossibility (fair coin tossing is impossible without an honest majority), and the hash-locked deposit that prices an abort, since preventing an abort is impossible.
6. Zero knowledge: interactive proofs, the Schnorr protocol, the Fully Homomorphic Encryption: Computing on Encrypted Data (FHE)-based construction and how soundness and zero knowledge are incorporated and the Fiat-Shamir transform (hashing the transcript to make proofs non-interactive).
7. Oblivious transfer: the definition, the transcript-consistency proof that AND is impossible information-theoretically and the two constructions. The animation shows both privacy properties on screen, so the viewer sees each property hold.

• Why is oblivious transfer complete for secure computation?: the AND gadget, then the protocols of GMW (Goldreich, Micali and Wigderson) or Yao.
• A protocol secure against semi-honest (follows the protocol and tries to learn extra information) but not malicious (deviates arbitrarily) adversaries: the ElGamal-based Oblivious Transfer (OT) of this lecture is the witness.
• What fairness is, and why fairness needs an honest majority: Cleve's bias argument (any two-party coin tossing protocol can be biased), and what deposits do instead.