Section 9: Advanced Topics

Everything so far has been about two verbs: encrypt and sign. Hide a message; vouch for a message. But the frontier of cryptography is stranger and more ambitious than that. This section tours four ideas that sound impossible until you see the trick: proving a statement is true without revealing why; computing on data while it stays encrypted; algorithms that survive an adversary armed with a quantum computer; and groups of mutually distrustful parties jointly computing an answer without anyone showing their input. None of this is science fiction — all four are deployed, standardized, or shipping in browsers today. What unites them is a shift in mindset: cryptography stops being a lockbox and becomes a way to control exactly what information a computation leaks — often, precisely zero.

Zero-knowledge proofs: proving without revealing

A zero-knowledge proof (ZKP) lets a prover convince a verifier that a statement is true while revealing nothing else — not the reason, not the evidence, not a single extra bit. "I am over 18" without showing a birthdate. "This transaction balances" without showing the amounts. "I know the password" without typing the password.

The classic intuition is the Ali Baba cave. Imagine a circular cave with one entrance that forks into two passages, A and B, which reconnect deep inside — but the connecting point is sealed by a magic door that opens only with a secret word. Peggy (the prover) claims she knows the word. Victor (the verifier) wants proof, but Peggy refuses to say the word aloud.

The protocol: Peggy walks in first and randomly disappears down A or B — Victor does not see which. Victor then walks to the fork and shouts a random demand: "come out of A!" (or B). If Peggy knows the word, she can always comply — if she happens to be in the wrong passage, she just opens the door and crosses over. If she does not know the word, she is stuck in whichever passage she picked and can only obey if Victor happens to name it: a 50% chance. One round proves little. But after 20 rounds, a faker survives only with probability (1/2)²⁰ — about one in a million. Crucially, Victor learns nothing about the word itself; all he ever sees is Peggy emerging from a passage he named, something he could have staged himself with a cooperative actress. That last observation is the essence of "zero knowledge": the transcript could have been faked, so it cannot contain real information.

Every zero-knowledge proof must satisfy three properties:

• Completeness — if the statement is true and the prover is honest, the verifier is always convinced. Peggy with the word always passes.
• Soundness — if the statement is false, no cheating prover can convince the verifier except with negligible probability. The faker gets caught, exponentially fast.
• Zero-knowledge — the verifier learns nothing beyond the truth of the statement. Formally: everything the verifier sees could have been simulated without the secret.

The cave protocol is interactive: it needs many live rounds of challenge and response. Most real applications want a non-interactive proof — a single blob anyone can verify later. The Fiat-Shamir transform achieves this in one elegant move: replace the verifier's random challenges with the output of a hash function over the transcript, so the prover effectively challenges herself in a way she cannot bias.

Modern proof systems compress this idea to an extreme. zk-SNARKs produce proofs of a few hundred bytes verifiable in milliseconds — for statements about arbitrarily large computations — but classically require a trusted setup ceremony whose leftover randomness ("toxic waste") must be destroyed, or an attacker could forge proofs. zk-STARKs drop the trusted setup and rely only on hash functions (which also makes them plausibly quantum-resistant), at the cost of proofs tens of kilobytes large.

Real deployments: Zcash uses zk-SNARKs to validate fully shielded transactions — the blockchain verifies that money was neither created nor stolen without seeing sender, receiver, or amount. zk-rollups (StarkNet, zkSync) bundle thousands of Ethereum transactions off-chain and post one succinct proof that all of them were executed correctly. And digital identity schemes are beginning to offer age verification without a birthdate: your ID issuer signs your data once, and you prove "the signed birthdate is before 2008" — nothing more.

Try being a verifier yourself. The classic demonstration for a claim like "these two balls are different colors" — made to a color-blind verifier — works exactly like the cave: the verifier randomly swaps or does not swap the balls behind their back, and asks the prover "did I swap?". A prover who can genuinely see the colors is always right; a liar facing identical balls can only guess.

What this demonstrates: each correct answer halves the chance the prover is bluffing, so confidence climbs as 1 − (1/2)ⁿ — yet you, the verifier, end the protocol still not knowing which ball is which color. You gained certainty about the statement ("they differ") and zero knowledge about the secret (the actual colors). That asymmetry is the whole trick.

Homomorphic encryption: computing on ciphertext

Normally, encrypted data is inert — to do anything useful with it you must decrypt it first, and the moment you do, whoever runs the computation sees your data. Homomorphic encryption breaks that trade-off: the ciphertexts themselves can be added or multiplied, and the result, when decrypted, equals what you would have gotten by computing on the plaintexts. The analogy: a locked glovebox in a jeweler's shop. You put raw gold inside and lock it; the jeweler works the metal through built-in gloves without ever opening the box; you unlock it and take out a finished ring. The worker computed on your material without ever possessing it.

There is a hierarchy of power:

• Partially homomorphic — one operation, unlimited times. Textbook RSA is multiplicatively homomorphic: Enc(a)·Enc(b) mod n = Enc(a·b), because (a^e)(b^e) = (ab)^e. Paillier is additively homomorphic: multiplying ciphertexts adds the plaintexts — which is why it shows up in voting schemes, where tallying is just addition.
• Somewhat homomorphic — both addition and multiplication, but only for a limited circuit depth before internal noise drowns the message.
• Fully homomorphic (FHE) — arbitrary computation on ciphertext. Considered a holy grail for 30 years, until Craig Gentry's 2009 breakthrough. His key insight, bootstrapping, is delightfully self-referential: the scheme homomorphically evaluates its own decryption function to refresh a noisy ciphertext into a clean one, resetting the noise budget so computation can continue forever.

Why endure that cost? Because some data must never be exposed: private cloud compute (the server processes your medical records without being able to read them), encrypted machine-learning inference (a model scores your encrypted input; the provider never sees your data, you never see their model), and private set intersection (two companies find common customers without either revealing its customer list — this is roughly how phones check your contacts against a breach database privately).

The widget below demonstrates the simplest real homomorphism with actual numbers: textbook RSA with a toy modulus. Watch two ciphertexts multiply into the valid encryption of the product — the "server" doing that multiplication never learned a, b, or a·b.

Post-quantum cryptography: surviving Shor

Every public-key scheme in this course so far — RSA, Diffie-Hellman, elliptic curves — rests on one of two problems: factoring large integers, or computing discrete logarithms. In 1994 Peter Shor showed that a sufficiently large quantum computer solves both efficiently. The mechanism, in one breath: both problems reduce to finding the period of a repeating function, and a quantum computer can put a function into superposition over all inputs at once and use a quantum Fourier transform to read off the period — the exact task classical machines find hopeless at scale. Period found, RSA factored, discrete log computed, private key recovered. Symmetric cryptography fares far better: Grover's algorithm gives only a quadratic speedup on brute-force search, effectively halving key lengths — AES-256 drops to 128-bit quantum security, which is still entirely comfortable. So the coming quantum transition is overwhelmingly a public-key problem.

NIST ran a public, worldwide competition from 2016 to select replacements, and in August 2024 published the first finished standards:

• ML-KEM (from Kyber, FIPS 203) — lattice-based key encapsulation, the general-purpose replacement for Diffie-Hellman and RSA key exchange.
• ML-DSA (from Dilithium, FIPS 204) — lattice-based digital signatures, the primary replacement for RSA/ECDSA signatures.
• SLH-DSA (from SPHINCS+, FIPS 205) — stateless hash-based signatures: slower and bigger, but resting only on hash-function security, as a conservative backup.

The lattice schemes are built on Learning With Errors (LWE). The intuition: solving a system of exact linear equations is trivial — high-school Gaussian elimination. But add a small random error to every equation, and the problem flips from trivial to (as far as anyone knows, even with a quantum computer) intractable: the noise poisons elimination, errors compound instead of canceling, and recovering the secret becomes equivalent to finding the closest point in a lattice of enormous dimension. The legitimate key holder is fine, because the scheme is engineered so the noise stays small enough to round away.

Exact equations (easy):          Noisy equations / LWE (hard):
  5a + 2b = 29                     5a + 2b = 29 + e1
  3a + 7b = 44   -> solve!         3a + 7b = 44 + e2      each e is a small
  ...                              ...                    unknown error
Gaussian elimination works.      Elimination amplifies the errors;
                                 recovering (a, b) is lattice-hard.
    

Hash-based signatures deserve their own intuition: commit to secret random values by publishing their hashes, then sign by selectively revealing preimages corresponding to the bits of the message digest. Forging requires inverting a hash. Merkle trees turn a pile of such one-time keys into one compact long-lived public key. Because the only assumption is "the hash function is good," SLH-DSA is the choice when you want minimal trust in new math.

Migration is not hypothetical. Chrome and Cloudflare already run hybrid X25519 + ML-KEM key exchange in TLS — a large share of Cloudflare-bound human traffic negotiates post-quantum protection today. The hybrid construction combines a classical and a post-quantum exchange, so security holds unless both are broken — insurance while the new math accumulates mileage.

Secure multi-party computation: joint answers, private inputs

Secure multi-party computation (MPC) asks: can several parties jointly compute a function of their private inputs so that everyone learns the output and nothing else? The founding puzzle is Yao's millionaires problem (1982): two millionaires want to know who is richer without either revealing their wealth. It sounds like it should require a trusted referee — MPC's achievement is that it does not. The protocol itself plays the referee, and provably leaks nothing beyond the answer.

The simplest gateway is additive secret sharing. To share a salary s among three parties, generate two random numbers r1, r2 and set the third share to s − r1 − r2 (mod some large number). Each share individually is uniformly random — a single share carries literally zero information about s, like one piece of a torn banknote. But shares are additively aligned: if everyone shares their own salary this way, distributes the pieces, and each party sums the pieces it holds, then the three per-party sums add up to the total of all salaries — while no party ever saw anyone else's actual number. Sum in hand, the average falls out.

Addition is the easy case. For arbitrary functions, Yao's garbled circuits do something remarkable: one party takes the function as a Boolean circuit and "garbles" it — replacing every wire value with a random cryptographic label and every gate with a little table of encryptions, so that holding the right input labels lets you decrypt exactly one output label per gate and nothing else. The other party obliviously obtains the labels for its own input bits (without revealing which bits) and then evaluates the whole circuit label by label, learning only the final output. The circuit runs; the inputs stay opaque; even the evaluator cannot tell what values flowed through the wires.

Real uses: Denmark ran a nationwide sugar-beet auction on MPC in 2008, matching farmers and the buyer at a fair clearing price with all bids kept private. Banks run joint fraud detection across institutions without pooling raw customer data. And distributed key generation — creating a key that exists only as shares, never assembled in one place — underpins the threshold systems in the next section.

Threshold cryptography: no single point of key compromise

A private key is a terrifying object: whoever holds it is you, and a single theft, insider, or subpoena captures it whole. Threshold cryptography dissolves the key into n shares such that any k of n can act (decrypt, sign) while any k−1 shares reveal nothing at all. Think of a bank vault needing any 3 of 5 officers' keys: no single rogue officer can open it, and losing one officer does not lock the vault forever. Both properties matter — threshold schemes buy security and availability at the same time.

The foundational construction is Shamir Secret Sharing (1979), and its engine is a fact you learned in school: two points determine a line; three points determine a parabola; k points determine a unique polynomial of degree k−1. To share a secret s with threshold k, hide s as the y-intercept of a random degree-(k−1) polynomial and hand each party one point on the curve. Any k parties can interpolate the polynomial (Lagrange interpolation) and read off f(0) = s. Any k−1 parties hold too few points: for every possible secret value, there is a polynomial through their points and that value — so their shares are consistent with every secret equally. That is not "hard to break"; it is information-theoretically perfect, secure against unlimited computing power, quantum or otherwise.

Threshold signatures push the idea further: the parties never reconstruct the key at all. Each holds a share forever, they run a small MPC protocol to produce signature fragments, and the fragments combine into one ordinary-looking signature. The private key exists only as a mathematical abstraction, never as bytes in any single machine's memory — there is nothing to steal in one place. This is how serious cryptocurrency custody works (exchanges splitting withdrawal keys across data centers and officers), how root key ceremonies protect the DNSSEC root and CA roots (multiple geographically separated smartcard holders), and how distributed certificate authorities remove the single HSM whose compromise would poison the whole trust chain.

Check your understanding

Where to learn more