Shamir Secret Sharing
Back up a crypto wallet recovery key across n family members so any t can help you recover it, but no smaller group can steal your funds. Apple uses this for iCloud Keychain; HashiCorp Vault uses it for seal keys.
—
Tap a blue dot on the stage to toggle it held or missing. Below threshold, ghost curves fan out — every one is an equally plausible secret.
Imagine a treasure map drawn not as a picture but as a curve. The secret is where the curve crosses the y-axis. You hand out n dots taken from the curve, one to each friend.
Here’s the magic: through any t dots there is exactly one curve of the right shape. Through fewer than t dots, infinitely many curves could fit — and the secret could sit anywhere on the y-axis. Your friends can’t tell which curve is real until enough of them meet up.
Move the sliders. Tap dots to remove them. When you have fewer than t dots, watch the ghost curves fan out: every one of those is an equally plausible map. When you cross the threshold, a single curve locks in and the secret shows up at the left edge.
Fix a prime field ℤq. To share a secret s with threshold t among n parties, the dealer picks random coefficients a1, …, at-1 ∈ ℤq and constructs the polynomial
f(z) = s + a1z + a2z² + … + at-1zt-1Share i is the point (i, f(i)), handed to party Pi. The secret is f(0) = s.
Reconstruction with any t shares uses Lagrange interpolation at z = 0:
s = Σi ∈ S f(i) · ∏j ∈ S, j ≠ i (−j) / (i − j)Fewer than t shares leave the remaining coefficient free to be anything — every candidate secret has exactly one consistent polynomial of degree t−1, so the posterior on s is still uniform.
Information-theoretic privacy, properly
Let T be any set of fewer than t parties. Conditioning on their shares {f(i)}i∈T, the remaining coefficients a|T|, …, at-1 are uniformly distributed over ℤqt−|T|. For every candidate secret s′, there exists a unique polynomial of degree t−1 passing through T’s points and hitting s′ at z=0. The secret is therefore information-theoretically hidden.
Why Lagrange works
The Lagrange basis polynomials Li(z) = ∏j≠i (z−j)/(i−j) satisfy Li(j) = δij. So Σi f(i)Li(z) is a degree t−1 polynomial agreeing with f on t points — which forces equality. Plug in z = 0.
The MPC payoff: Shamir is linear
Let [x] denote a Shamir sharing of x. Then [x + y] is the pointwise sum of share vectors — no interaction. Multiplication by a public constant is free. Multiplication of two sharings doubles the polynomial degree; the BGW protocol restores it via a one-round degree reduction, yielding perfectly secure MPC against t < n/2 passive corruptions, and t < n/3 with active verifiable secret sharing.
Bridge: additive sharing (Share) is Shamir with t = n and a constant polynomial—every coefficient except a0 set to zero. The linearity story is the same; Shamir just trades unanimity for a threshold.
Yao’s Garbled Circuits
Alice and Bob are deciding whether to grab coffee. Neither wants to admit interest alone. They want to know only whether both said yes — the classic “crush problem,” computed as a single AND gate.
—
One AND gate is the whole circuit here. Real systems chain thousands of gates this way — Yao’s ideas power Signal’s private contact discovery and Apple’s private set intersection.
Alice and Bob want to know who has more money. Neither will whisper their number. So they build a little machine out of locked boxes.
Alice, the builder, makes the machine first. Every wire in the machine has two secret labels: one means zero, one means one. Alice picks them at random and tells no one which is which. For each gate she writes down all four possible outputs, but locks each line with the two input labels that would trigger it. She scrambles the order so you can’t tell by position.
She hands the locked machine to Bob along with her own input labels — just the labels, not their meaning. Bob gets his own labels through a clever trade called oblivious transfer: Alice offers both, Bob picks one, and neither learns anything extra.
Bob walks through the machine. At every gate he has exactly two labels; exactly one row unlocks. He carries the output label forward. At the end, Alice reveals just the final label’s meaning. That’s the answer. Nothing else escapes.
Fix a boolean circuit C the two parties agree on. The garbler (Alice) does:
1. Label every wire. For each wire w, sample two random k-bit labels Lw0 and Lw1. These strings reveal nothing about the bit they stand for.
2. Garble every gate. For a gate g with inputs a, b and output c computing c = g(a,b), compute four ciphertexts
ELaα(ELbβ(Lcg(α,β))) for (α,β) ∈ {0,1}²and permute them randomly. This is the garbled table.
3. Transmit. Send the garbled tables and Alice’s own input labels LwxA,w. For each of Bob’s input wires, run 1-out-of-2 oblivious transfer so Bob learns LwxB,w and nothing about Lw1−xB,w; Alice learns nothing about Bob’s choice.
4. Evaluate. Bob holds exactly one label per wire he’s processed. For each gate he attempts to decrypt all four rows; exactly one decrypts correctly (verified by a tag or an all-zero check) and yields the output-wire label.
5. Decode. For output wires, Alice sends the mapping Lout0→0, Lout1→1. Bob learns the output bits and nothing else.
Security in one sentence
If E is an IND-CPA-secure symmetric encryption scheme, then the garbled circuit is indistinguishable from a simulator that knows only the circuit topology and the output — a standard sequence-of-hybrids argument peels labels away one gate at a time, replacing unopened ciphertexts with encryptions of zero.
Point-and-permute
Attach a random permutation bit πw ∈ {0,1} to every wire. Publish labels as (Lwb, b ⊕ πw). The two pointer bits on the input labels index directly into the row the evaluator should decrypt — no trial decryption, no verification tag. Bob still can’t tell what bit he holds because πw is secret.
Free-XOR and half-gates
Pick a global secret Δ and set every pair of wire labels to satisfy Lw1 = Lw0 ⊕ Δ. Now XOR gates cost zero ciphertexts: the evaluator simply XORs input labels. The half-gates construction shrinks every AND gate to two ciphertexts, provably optimal under standard assumptions (Zahur, Rosulek & Evans, EUROCRYPT 2015).
Why this is two-party
Only the garbler knows all labels; only one evaluator walks the circuit. The BMR protocol lifts the idea to n parties by having them jointly garble — but the per-gate cost jumps to O(n) ciphertexts and the round count collapses to constant, a tradeoff you don’t want for hundreds of parties.
Bridge: Shamir (Split) stays efficient as parties grow but needs rounds per multiplication. Yao gets constant rounds for two parties but poor scaling. Real systems (e.g., SPDZ, ABY3) mix them.
Zero-Knowledge Proofs
Peggy claims she knows a magic word that opens the back door of a cave. Victor wants proof — without ever learning the word. The Ali Baba cave protocol is the canonical intuition behind zk-SNARKs, zk-STARKs, and every zk-rollup running on Ethereum today.
—
Run many rounds. An honest Peggy always passes. An impostor gets caught with probability 1/2 per round, so after n passed rounds Victor’s confidence is 1 − 2−n.
Imagine a cave shaped like a horseshoe. Two entrances, call them Left and Right, meet at a back wall with a magic door. The door only opens for someone who knows a secret word. Peggy claims to know it. Victor doesn’t believe her and wants proof — but if Peggy whispers the word, he could walk in himself. So she proves it like this.
Victor waits outside. Peggy walks in through either entrance, at random, out of his sight. Then Victor shouts “Left!” or “Right!” — also at random. If Peggy is already on the side he named, she walks right back out. If she’s on the other side, she uses the magic word to cross through the door and emerges from the side he named.
Either way, Victor sees Peggy come out from the correct side. Did she know the word, or did she just guess the right entrance? One round, he can’t tell — it’s 50/50. But they can repeat. After twenty rounds in a row, an impostor’s chance of luck is one in a million. Peggy proved knowledge without once revealing the word.
Toggle whether Peggy actually knows the secret. Click “Run a round” repeatedly. Watch the confidence meter.
The Ali Baba cave is a Σ-protocol for proof of knowledge: three messages — commitment, challenge, response — repeated to drive soundness error toward zero.
Commitment: Peggy picks e ∈ {L, R} uniformly and walks into entrance e. She is committed to a side.
Challenge: Victor picks c ∈ {L, R} uniformly and publishes it.
Response: Peggy emerges from side c. This requires crossing the door iff e ≠ c — possible only with the secret.
Soundness: if Peggy does not know the secret, she can guess c with probability 1/2 before committing and match. After n successful rounds, Pr[impostor passes all] = 2−n.
Zero-knowledge: Victor’s transcript is (e, c, emerges-from-c). A simulator without the secret can produce an indistinguishable transcript by choosing c first and then setting e = c. Victor learns nothing beyond “Peggy knows the secret.”
Completeness, soundness, zero-knowledge
A proof of knowledge for relation R = {(x, w) : P(x, w)} is a protocol satisfying:
- Completeness: honest Peggy knowing
walways convinces honest Victor. - Soundness: a cheating Peggy without
wconvinces Victor with probability ≤ negligible. - Zero-knowledge: Victor’s view can be simulated without
w.
The cave protocol instantiates all three. Its soundness error 2−n after n rounds is an instance of parallel amplification.
From interactive to non-interactive
The Fiat-Shamir transform replaces Victor’s random challenges with c = H(statement, commitment) for a collision-resistant hash H. This makes the proof a single message Peggy can post publicly. zk-SNARKs (Groth16, PLONK, STARKs) are Fiat-Shamir applied to very elaborate algebraic Sigma-protocols over polynomial commitments.
Real deployments
zk-rollups (Scroll, Linea, zkSync, Polygon zkEVM, StarkNet) post succinct SNARK/STARK proofs to Ethereum to compress thousands of transactions into a single validity proof. Tornado Cash and Aztec use SNARKs for private payments. Polygon ID and Semaphore issue verifiable credentials (e.g. “I am over 18” without revealing birthdate). World ID uses ZK to prove uniqueness without revealing biometrics.
Bridge: ZK composes with MPC — in malicious-security MPC, parties attach ZK proofs to each message attesting they followed the protocol honestly (see Yao → Math).