Implementing ML-KEM from the standard, with no dependencies

Post-quantum cryptography is easy to talk about and hard to hold in your head. I wanted to actually hold it, so I implemented ML-KEM, the key encapsulation mechanism NIST standardised as FIPS 203 and which most people still call Kyber, from the specification text alone. No cryptographic libraries, no reference code copied in. Only Python and the document.

Why implement it from the specification

Calling a library teaches you an API. Writing the algorithm teaches you where the difficulty actually lives, and in lattice cryptography the difficulty is almost entirely in polynomial arithmetic.

ML-KEM operates on polynomials in the ring Z_3329[X]/(X^256 + 1). Every encapsulation multiplies polynomials together. Done naively, that multiplication is quadratic: 256 coefficients against 256 coefficients, 65,536 operations for a single product. The scheme would be unusably slow. The number-theoretic transform is what makes it practical.

The transform is the whole game

The NTT is a discrete Fourier transform over a finite field instead of the complex numbers. It converts polynomial multiplication into pointwise multiplication, taking the cost from quadratic to n log n.

Kyber's ring has a subtlety worth stating plainly: X^256 + 1 does not split completely over Z_3329, because 3329 supports 256th roots of unity but not 512th. So the transform bottoms out at 128 quadratic factors rather than 256 linear ones, and the pointwise step multiplies degree-one polynomials modulo those factors. That is why the implementation carries a quadratic CRT layer where a textbook FFT would just multiply numbers.

I measured the payoff rather than assuming it: roughly 4.4 times faster than schoolbook multiplication, verified against an independent oracle so a fast wrong answer could not pass as a fast right one.

![Implementation architecture, from the FIPS byte API down to the polynomial ring]

What correctness meant here

Cryptographic code that looks right and is wrong is worse than code that fails loudly, so the test suite came before the optimisation. Twenty-five deterministic seeded tests cover:

• NTT round trips, forward then inverse, back to the original coefficients
• Known-answer vectors for centred binomial distribution sampling
• Implicit rejection, where a malformed ciphertext must produce a deterministic wrong key rather than an error, so an attacker learns nothing from the failure mode
• FIPS-sized byte APIs across all three parameter sets, ML-KEM-512, 768, and 1024

What it does not do

This matters more than the benchmark. The implementation is not constant time. Its runtime depends on secret data, which means it leaks through timing side channels and must never guard anything real. It is also not FIPS validated, and validation is a formal process this has not been through.

I document those boundaries in the repository because an implementation that hides its limitations is worse than no implementation. The purpose here is understanding, and understanding includes knowing exactly what you have not solved.

What I would do next

The natural continuation is constant-time discipline: branch-free conditional selection, memory access patterns independent of secrets, and timing measurement under load rather than trusting inspection. That is a different project with a different standard of proof, and it is the direction I find most interesting.

Source: PQC-Lattice-Sandbox