Secret sharing. Multi-Party Computation (MPC) with an honest majority.

Lecture 22 gave the general two-party solution. Yao's protocol represents the function as a Boolean circuit, assigns two random labels to every wire, and replaces each gate by its truth table with the output label double-encrypted under the two input labels; padding lets a wrong row be recognized and a random permutation of the four rows hides which one worked. The garbler sends the tables and the labels for its own input bits; the evaluator obtains one label per its own input bit by oblivious transfer, then decrypts exactly one row per gate up to the output. The evaluator holds one label per wire and never learns the bit it denotes. Against a malicious garbler: cut-and-choose over $k$ copies bounds cheating, majority output removes the leak in aborting on disagreement, committed inputs with zero-knowledge proofs enforce input consistency, and OT on committed inputs defeats selective failure. Fairness remained out of reach.

Everything so far has been two-party, constant-round and unfair. This lecture changes all three by changing the representation. Garbling encrypted the circuit; in this lecture each value in the computation stays split across the parties so that no admissible coalition can read it. The parties compute on the pieces.

The primitive is secret sharing. For the extreme threshold $t = n-1$ a one-time-pad argument suffices: the parties receive random shares. The last share absorbs the secret. Shamir's scheme gets every intermediate threshold from a single algebraic fact. The secret is the value $p(0)$, the remaining $t$ coefficients are drawn uniformly, and party $i$ receives the value $p(i)$. Any $t+1$ shares interpolate the polynomial and recover the secret; any $t$ shares are consistent with every candidate secret exactly once each, so the coalition's posterior equals its prior. That privacy is information-theoretic: it holds against an unbounded adversary, unlike any guarantee in the previous two lectures.

The second half turns sharing into computation. The function becomes an arithmetic circuit. Each party shares its input. The invariant is that every wire value is shared with threshold $t$. Addition and multiplication by a public constant are free, computed locally, because sharing is a linear map. Multiplication breaks the structure: the local products encode the product, but as a polynomial of degree $2t$, and iterating doubles the degree again. The repair is a re-sharing step in which each party freshly shares its own product share and everyone takes the same Lagrange combination, costing one round per multiplicative layer. Finally, an honest majority achieves what two parties cannot: with $t < n/2$ the honest parties alone hold enough shares to reconstruct, so aborting withholds nothing, and both fairness and guaranteed output delivery hold. The GMW (Goldreich, Micali and Wigderson) compiler upgrades the protocol to malicious security by having each party prove in zero knowledge that its messages were computed correctly.

1. Secret sharing: the definition of a $t$-out-of-$n$ scheme, the additive $t = n-1$ construction, then Shamir's scheme with Lagrange reconstruction, a worked reconstruction over $\mathbb{F}_{17}$ and the privacy computation written out.
2. The interpolation animation, in the same section. The point lies in the final two steps: several distinct polynomials pass through the same $t$ points and take different values at zero.
3. The Shamir lab: once the secret, the threshold and the number of parties are set, pooling subsets of shares shows reconstruction succeeding at $t+1$ and becoming impossible at $t$. The arithmetic is done in a real prime field with modular inverses.
4. Linearity, variants and threshold cryptography: why sums of shares share the sum; verifiable, robust and non-malleable sharing; and distributed signing. The additive-sharing lab in the same section shows local multiplication failing and names the missing cross terms.
5. Multi-Party Computation (MPC) with an honest majority: arithmetic circuits, input sharing, free additions, the degree-reduction trick for multiplication, output reconstruction and the GMW (Goldreich, Micali and Wigderson) compiler.

• Prove that $t$ shares reveal nothing: the bijection between polynomials of degree $\le t$ and their values at $t+1$ points, done carefully.
• Why multiplication needs interaction, and why degree reduction preserves the secret: both halves of the argument, including why re-randomization is needed as well as degree reduction.
• What fairness is, and why it needs an honest majority: the exercise that vindicates the honest-majority hypothesis of this lecture.