Post-Quantum Cryptography (ML-KEM): The Math

ML-KEM (Module-Lattice-Based Key Encapsulation Mechanism), formerly known as CRYSTALS-Kyber, is the post-quantum key exchange algorithm standardized by National Institute of Standards and Technology as FIPS 203. Its security is based on the difficulty of certain problems in lattice cryptography, which are believed to remain hard even for quantum computers.

Traditional public-key cryptography relies on problems like:

• Integer factorization (RSA)
• Discrete logarithms (DH, ECDH)

Quantum computers can solve these efficiently using the scientific concept Shor’s Algorithm.

ML-KEM instead relies on problems involving high-dimensional lattices.

What Is a Lattice?

A lattice is a regular grid of points extending through many dimensions.

In 2D:

where v1 and v2​ are basis vectors. A basis vector is one of the fundamental building blocks used to describe positions, directions, and transformations in a vector space.

Think of basis vectors as the coordinate system’s “building blocks.” Every vector in the space can be created by combining them.

In ordinary Cartesian coordinates, the standard basis vectors are:

and

These represent:

• One unit in the x-direction
• One unit in the y-direction

Any vector can be expressed as a combination of them.

A lattice can be visualized as all integer combinations of basis vectors. Using the 2D basis vector given above, the lattice consists of all integer combinations of these vectors. This produces every point with integer coordinates:

Points include: (0,0), (1,0), (2,3), (-4,1), and infinitely many others. This is called the integer lattice and is usually written:

In ML-KEM, we’re not dealing with 2D lattices. We’re dealing with lattices in hundreds of dimensions where geometric intuition breaks down, unless you are a fantastically unusual human being.

The Hard Problem

ML-KEM is ultimately built on the difficulty of variants of the Learning With Errors (LWE) problem.

The simplified form is:

Given many equations:

where:

• A is known
• b is known
• s is secret
• e is small random noise

Recover s.

Without the noise term e, this would just be linear algebra.

The noise makes the problem extraordinarily difficult in high dimensions.

Why Noise Matters

Suppose you know:

Then solving for s is straightforward.

Now add a small error:

Suddenly:

• Every equation is slightly wrong.
• Traditional matrix inversion no longer works cleanly.
• Finding the correct secret becomes equivalent to solving difficult lattice problems.

This “noise” is what gives lattice cryptography its security.

From LWE to Module-LWE

Raw LWE is secure but inefficient.

ML-KEM uses a more structured version called Module-LWE. Think of the progression:

Module-LWE provides:

• Smaller keys
• Faster computation
• Better practical performance

while retaining strong security arguments.

Polynomial Arithmetic

Instead of ordinary integers, ML-KEM works with polynomials.

For example:

Operations occur in a special polynomial ring:

This means:

• coefficients are reduced modulo q
• polynomials are reduced modulo x²⁵⁶ + 1

The ring used by ML-KEM has:

This specific choice enables extremely efficient arithmetic.

Matrix Multiplication with Polynomials

Instead of integer matrices:

ML-KEM uses matrices whose entries are polynomials.

The public key computation resembles:

where:

• A is a matrix of polynomials
• s is a secret polynomial vector
• e is a noise vector

This is the Module-LWE problem.

Why the Number Theoretic Transform Matters

Polynomial multiplication is expensive.

Naively multiplying two degree-255 polynomials requires many operations.

ML-KEM uses the mathematical equivalent of the FFT:

(Number Theoretic Transform)

This converts polynomial multiplication into point-wise multiplication.

Conceptually:

becomes:

which is dramatically faster.

A large part of ML-KEM’s performance comes from NTT optimization.

Encapsulation and Decapsulation

Unlike Diffie-Hellman, ML-KEM is a Key Encapsulation Mechanism.

Encapsulation

The sender:

1. Generates random values.
2. Uses the recipient’s public key.
3. Produces:

• a ciphertext
• a shared secret

Decapsulation

The recipient:

1. Uses the private key.
2. Processes the ciphertext.
3. Recovers the same shared secret.

Both sides now possess identical secret material that can be used in TLS.

Why Quantum Computers Don’t Break It

Known quantum algorithms provide only limited speedups against lattice problems.

The best known attacks use variants of lattice reduction algorithms such as:

• BKZ
• Sieving methods

Quantum computers help somewhat, but there is currently no lattice equivalent of Shor’s algorithm.

This means security degrades much more slowly under quantum attack than RSA or ECC.

Security Intuition

You can think of ML-KEM as:

1. Creating a huge high-dimensional geometric structure.
2. Hiding a secret inside it.
3. Adding carefully chosen noise.
4. Allowing legitimate users to remove the noise.
5. Leaving attackers with a problem that appears computationally infeasible.

The legitimate recipient knows enough secret information to distinguish the signal from the noise; an attacker only sees an enormous noisy lattice problem.

Summary

ML-KEM replaces the number theory behind RSA and elliptic curves with high-dimensional lattice mathematics, where recovering a secret hidden inside noisy polynomial equations appears intractable for both classical and currently known quantum algorithms.

Notes

• AI / GenAI / ChatGPT / etc were not used to generate the text of this article.
• ChatGPT was used to generate the images.
• I used em dashes in my writing before the current GenAI wave was a thing. Not planning on changing now.
• Names have been changed to protect the guilty.
• None of the hostnames or users used in examples actually exist.
• Feel free to post any comments or suggestions below.