Chapter 3: Lattices and Learning With Errors

01.What this chapter is for

Chapter 2 ended with a promise it did not keep. It said the replacement for factoring and discrete logarithms is lattice-based, and then declined to say what a lattice is. This chapter says.

By the end you should be able to state the new hard problem precisely, compute a small instance of it by hand, and explain why a quantum computer does not obviously help with it. That last part matters most. The whole argument of Chapter 2 was that both classical problems were secretly the same problem, periodicity, and that Shor's algorithm finds periods. If the replacement had a hidden period too, the entire migration would be pointless.

The chapter arrives at a problem called Learning With Errors, and the one-sentence version is that it is ordinary schoolbook simultaneous equations with a small amount of noise added to each equation. Without the noise a student solves it in minutes. With it, nobody knows how to solve it at all, classically or quantumly. Watching that switch flip is the point of the chapter.

02.Who this is written for

The same reader as the first two chapters. No prior linear algebra is assumed. Vectors are introduced as lists of numbers before anything is done with them, and the only geometry used is the plane you can draw on graph paper.

Modular arithmetic from Chapter 1 is needed for the second half, because Learning With Errors lives in $\mathbb{Z}_q$. Nothing from Chapter 2 is needed except the idea of a trapdoor, which is restated here where it is used.

03.Reading order

The chapter has two halves. Notes 1 to 5 are geometry, done in two dimensions on paper. Notes 6 to 9 move into modular arithmetic and build the actual cryptographic problem.

1. Vectors and the Plane. Vectors as lists of numbers. Adding, scaling, and what a linear combination is.
2. What a Lattice Is. The one change that turns a plane into a lattice, and a worked skewed grid you can plot.
3. Good and Bad Bases. The same lattice described two ways, one useful and one useless. This is where the trapdoor comes from.
4. Measuring a Lattice: Determinant and Minkowski's Theorem. How to measure a lattice, and the 1889 theorem that says a short vector has to exist.
5. Short Vectors: SVP and CVP. The two hard problems, and why height of dimension is what makes them hard.
6. Noise Breaks Linear Algebra. Solving equations modulo $q$ is easy. Adding one unit of noise makes it impossible, demonstrated on a $3 \times 3$ system.
7. The Learning With Errors Problem. The definition, the search and decision forms, and a full instance over $\mathbb{Z}_{17}$.
8. Where the Noise Comes From. Where the noise comes from, and why the standards use a distribution a Gaussian purist would not have chosen.
9. From LWE to the Deployed Schemes. From plain LWE to the ring you built in Chapter 1, and the chapter summary.

04.A note on dimension

Every picture in this chapter is two-dimensional, and every hard problem in this chapter is easy in two dimensions. That is not a flaw in the exposition. It is the single most important fact about lattices.

In the plane you can look at a lattice and see the shortest vector immediately. In three dimensions you can still more or less see it. By dimension $40$ the best known algorithms are struggling, and the lattices inside ML-KEM have dimension $256$ per polynomial and several polynomials stacked. Nothing about the problem changes as the dimension grows. What changes is that the number of candidate combinations you would have to look through stops being a number anyone can write down.

So read the pictures as intuition about what is being asked, never as evidence about how hard it is. The difficulty lives entirely in a dimension you cannot draw.