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