The Road Forward

This chapter has argued that the public-key layer of the Internet rests on two problems, that both fail to the same quantum algorithm, and that lattice-based schemes over the ring $R_q$ are what the standards bodies chose instead. The rest of the book is about those schemes.

01.What each remaining chapter does

Chapter 3, Lattices and Learning With Errors. The new hard problem, built from scratch. A lattice is introduced concretely, as a grid of points generated by adding and subtracting a few fixed vectors, before any general definition appears. The chapter then develops Learning With Errors, which is the problem of solving a system of linear equations when every equation has had a small amount of noise added to it. Without the noise the system falls to schoolbook elimination in seconds. With it, the problem is believed hard for classical and quantum machines alike. That single change is what the security of both standards rests on, and this is the first chapter where the replacement trapdoor is actually stated.

Chapter 4, the Number Theoretic Transform. The speed chapter, and the reason $R_q$ specifically. Multiplying two polynomials of length $n$ the schoolbook way costs about $n^2$ coefficient multiplications. For $n = 256$ that is around $65{,}000$ per product. The Number Theoretic Transform brings it down to about $n \log n$, roughly $2{,}000$, and it is the same idea as the Fast Fourier Transform carried out in modular arithmetic instead of over the complex numbers. Every serious implementation of both standards spends most of its time here, which makes it the natural target for a hardware accelerator.

Chapter 5, ML-KEM. The key encapsulation mechanism, specified in enough detail to implement, working from FIPS 203. How keys are generated, how encapsulation and decapsulation work, what the parameter sets are, and where the noise from Chapter 3 enters.

Chapter 6, ML-DSA. The signature scheme, from FIPS 204, at the same level of detail. Signing and verification, the rejection-sampling loop that makes signatures leak nothing about the private key, and the parameter sets.

Chapter 7, Modular Reduction and Keccak. The engineering primitives underneath everything above. Barrett, Montgomery and Plantard reduction, which are three ways to compute $a \bmod q$ without a division instruction, and the Keccak sponge that supplies hashing and pseudorandomness to both standards. This is the chapter closest to hardware.

02.What this book does not cover

Hash-based and code-based post-quantum cryptography are not developed here, and the omission is deliberate rather than an oversight.

Hash-based signatures, including the standardised SLH-DSA, rest on the most conservative assumptions in the field. They are the right choice when a signature must remain valid for decades and size does not matter, such as signing firmware for a device that will outlive several migrations. Their signatures are one to two orders of magnitude larger than ML-DSA's.

Code-based key encapsulation, principally Classic McEliece, has an extraordinary track record, unbroken since 1978. Its public keys run to hundreds of kilobytes, which rules it out for a protocol handshake even where it is ideal for a long-lived static key.

Both are worth knowing about, and neither is where the volume of Internet traffic will go. Lattice schemes are what the long tail of connections will run on for the next decade or two, and they are where both the software and the hardware engineering opportunity is largest.

03.Chapter summary

Symmetric cryptography needs a shared key, and two strangers cannot establish one over a channel an eavesdropper is listening to. Public-key cryptography solved that in the 1970s with the trapdoor one-way function: easy forwards, infeasible backwards, easy backwards again for whoever holds the secret.

Two arithmetic problems have supplied that function ever since. Integer factoring, which RSA uses, and the discrete logarithm problem, which Diffie-Hellman and the elliptic-curve schemes use. Both look easy at pencil scale and become impossible at deployed scale, which is exactly the property the contract demands.

Both are also, underneath, questions about periodicity. Shor's 1994 algorithm finds periods in polynomial time on a sufficiently large quantum computer, so both fall to one machine running one algorithm. No such machine exists yet, and harvest-now-decrypt-later already makes that irrelevant for any secret that must last twenty years.

NIST's 2016 to 2024 competition standardised three replacements. ML-KEM and ML-DSA are lattice-based and are the defaults. SLH-DSA is hash-based and exists so that a break in lattice mathematics would not take everything at once. Lattices won on security, on size, and above all on speed, and their speed comes from being able to multiply quickly inside $R_q$.

Which is the ring Chapter 1 built. The next chapter says what a lattice is and what makes Learning With Errors hard.