Chapter 2: Why Post-Quantum Cryptography?

01.What this chapter is for

This chapter does no algebra at all. Chapter 1 built the ring $R_q = \mathbb{Z}_q[X]/(X^n + 1)$ from nothing, and a fair question at the end of it is why anyone would want that particular object. This chapter answers that question, and it answers it as a story rather than as mathematics.

The story has four parts. There is a problem that cryptography spent most of the twentieth century unable to solve, which is how two strangers who have never met can agree on a secret over a channel that everybody can hear. There is the solution found in the 1970s, which is a specific and rather beautiful trick called a trapdoor one-way function. There are the two pieces of arithmetic that trick has been built out of ever since, both of which a large enough quantum computer would demolish in an afternoon. And there is what the standards bodies decided to do about that, which is where lattices, and therefore $R_q$, come in.

By the end you should be able to say precisely what breaks, why it breaks, and why the replacement was built out of the algebra you have already learned.

02.Who this is written for

The same reader as Chapter 1. First semester of college, no prior cryptography of any kind, no prior physics. Words like encryption, public key, qubit and polynomial time are all defined here before they are used, and every one of them is introduced with a small worked example first.

The only background this chapter assumes is modular arithmetic, because both of the classical hard problems are stated in it. If $a \bmod n$ and the congruence symbol $\equiv$ are not yet routine, read Modular Arithmetic before starting here. Nothing else from Chapter 1 is needed.

03.Reading order

The notes are meant to be read in order, and each one is short.

1. What Cryptography Is Trying To Do. Alice, Bob, and Eve. What a key is, what symmetric encryption is, and the one problem it cannot solve.
2. Public-Key Cryptography and the Padlock Idea. The 1976 idea, explained with padlocks before any numbers appear.
3. One-Way Functions and Trapdoors. Turning the padlock picture into a mathematical contract with three clauses. This note also explains what "easy" and "hard" mean when a cryptographer says them.
4. Factoring and RSA. The first of the two classical hard problems, with a complete worked RSA example small enough to check on paper.
5. Discrete Logarithms and Diffie-Hellman. The second one, with a complete worked key exchange.
6. Shor's Algorithm and the Quantum Threat. What a quantum computer actually is, and why one algorithm from 1994 takes down both problems at once.
7. Post-Quantum Cryptography and the NIST Competition. The eight-year search for replacements, and the three standards that came out of it.
8. The Road Forward. Which of those standards this book follows, and what the remaining chapters do.

04.A note on sizes

Chapter 1 kept the numbers small so that every residue class fitted on the page. This chapter does the same, and here the gap between the pencil-scale example and the deployed scale is the entire point rather than a convenience. RSA is demonstrated with $p = 11$ and $q = 13$. Real RSA uses primes of about 300 digits each. Diffie and Hellman are demonstrated modulo $17$. Real Diffie and Hellman work modulo a prime of several hundred digits.

In both cases the pencil version is broken in a few seconds by hand, and that is exactly what you should expect. The security does not come from the shape of the arithmetic. It comes from how badly the backward direction scales while the forward direction stays cheap. Watching that gap open up on small numbers is the best preparation for believing what happens at large ones.

05.Where this leads

The last section of this chapter names lattices as the winning replacement without saying what a lattice is. That is deliberate, because the answer takes a chapter of its own. Chapter 3 introduces lattices and the Learning With Errors problem from the ground up, and it is the first place in this book where the new hard problem is actually stated. The ring $R_q$ you built in Chapter 1 is where that problem eventually gets to live.