Introduction to Kyber (ML-KEM)

Every code listing from this chapter of Applied Post-Quantum Cryptography — 15 in total, 15 runnable here. Edit any cell and press Run.

The book's snippets build on each other down the chapter, but a Sage Cell kernel runs one cell and keeps no state afterwards, so each cell replays the earlier listings with apqc_book. That call is the only thing added to the book's own code.

← the playground

Listing 1 — Simplifications used in the toy version

The real ML-KEM standard uses many sophisticated mechanisms. In the toy version, we keep only the core idea:

Although these simplifications are significant, the mathematical skeleton remains the same. For the module dimension we also shrink k from 2,3,4 down to k=2, so that the objects are easy to inspect by hand.

Listing 2 — Set up the ring

We define a polynomial ring modulo x⁸+1. Every object we build from here on lives in this quotient ring R_q.

Listing 3 — Set up the ring

Listing 4 — Build the module: vectors and matrices of polynomials

For Kyber512, the module dimension is k=2. That means the secret is not one polynomial but a vector of k polynomials, and the public matrix A is a k × k matrix of polynomials.

Listing 5 — Create small noise

In real Kyber, the noise is sampled from a centered binomial distribution (CBD), which is the subject of a later chapter. For the toy version, we simply use small coefficients in the range {-1,0,1}.

Listing 6 — Key generation

The module-LWE form is very close to the standard LWE form:

We implement it as follows.

Listing 7 — Verify the key generation process

We can print the matrix and the resulting public value to check that the shapes and types match expectations.

Listing 8 — Encoding a message bit

For the toy version, the message is reduced to a single bit. In the real scheme, message encoding is far more subtle; here we simply map a bit to either zero or a value near the middle of the modulus range.

Listing 9 — Encryption

To encrypt a message bit, we sample a random vector r and two noise terms e₁,e₂. The core equations are

Listing 10 — Decryption

The decryption step uses the secret key s. The main idea is that the terms involving A and s cancel out during the algebraic expansion, leaving only a small amount of noise and the encoded message.

Listing 11 — Decryption

We recover the bit by comparing circular distances to the two encoding centres, 0 and ⌊ q/2⌋. In particular, the field element 16 represents -1 and must be recognised as close to encoded zero, not as a message-one value.

Listing 12 — Putting everything together

A complete toy run looks like this.

Listing 13 — Why the scheme can fail sometimes

This toy construction can still fail frequently because q=17 is tiny and the accumulated error is not bounded as in ML-KEM. It illustrates cancellation and circular decoding, not a reliable encryption scheme. In real ML-KEM, the parameters are tuned so that the decryption failure probability is extremely small.

A simple experiment is to change the noise generator from

Listing 14 — Why the scheme can fail sometimes

to something larger, such as

Listing 15 — Why the scheme can fail sometimes

or even