Chapter 5: ML-KEM

01.What this chapter is for

Four chapters of groundwork are now behind us. Chapter 1 built the ring $R_q$, Chapter 2 explained why a replacement was needed, Chapter 3 gave the hard problem, and Chapter 4 made the arithmetic fast.

This chapter assembles them into a shipped standard. ML-KEM is FIPS 203, published by NIST in 2024, and it is what your browser will use to agree a session key with a web server. Everything in it is built from pieces already on the page.

By the end you should be able to follow every step of key generation, encapsulation and decapsulation, explain why decryption recovers the message, say precisely what the failure probability means, and compute a complete toy instance by hand.

02.Who this is written for

The same reader as before, though this chapter assumes more of the earlier ones than any so far. Specifically it needs polynomial arithmetic in $R_q$ from Chapter 1, the Module-LWE sample shape from Chapter 4, and the centred binomial distribution from Chapter 3. Nothing new is introduced from outside those.

One thing this chapter does not do is prove security. The reduction from ML-KEM to Module-LWE is a real piece of work and it is not reproduced here. What is given instead is the algebra of correctness, meaning why the scheme decrypts to the right answer, which is short enough to follow line by line and is the part an implementer has to understand.

03.Reading order

1. What a KEM Is. The narrow job the scheme does, and why it is not simply "encrypt a random key".
2. The KEM Contract. Three algorithms, and the two attacker models that shape the design.
3. The Parameter Sets. What varies across the three security levels and what does not.
4. Key Generation. Producing a public and secret key.
5. Encryption. The seven steps of the encryption layer, including how a message bit becomes a coefficient.
6. Why Decryption Works. The cancellation that makes the whole thing function, and the noise bound it leaves behind.
7. Compression and Ciphertext Size. Throwing away bits on purpose, and where the published byte counts come from.
8. The Fujisaki-Okamoto Wrapper. Turning a scheme that survives eavesdroppers into one that survives tampering.
9. A Worked Toy Example. A complete instance over $\mathcal{R}_{17}$ with every number computed, and the chapter summary.

04.Two layers, and why

The one structural fact worth knowing before starting is that ML-KEM is built in two layers, and they have different characters.

The inner layer is a public-key encryption scheme built directly on Module-LWE. All the lattice mathematics lives here. It is secure against an attacker who only listens.

The outer layer is a generic wrapper called the Fujisaki-Okamoto transform. It contains no lattice mathematics at all and would work over any encryption scheme with the right properties. Its job is to upgrade the guarantee so the scheme also survives an attacker who tampers with ciphertexts.

Notes 4 through 7 build the inner layer. Note 8 wraps it. Keeping the two apart is what makes the design comprehensible, and it is also how FIPS 203 is organised.

05.A note on the worked example

The toy example in note 9 uses $\mathcal{R}_{17}$ with $n = 4$ and $k = 2$, which is small enough to compute entirely by hand.

It contains something the earlier chapters' examples did not: a genuine decryption failure. One coefficient of the noise comes out larger than the tolerance allows, and the scheme gets that coefficient wrong. That is not a mistake in the example. It is what happens when $q = 17$ leaves almost no margin, and it is the most direct way to see why the real parameter sets are chosen the way they are.