Post-Quantum Crypto, in depth: learning with errors, Module-LWE and how ML-KEM is built

Learning with errors

Take a secret vector s of length n with entries mod q. If I give you many pairs (a, a . s mod q) with random a, you recover s by Gaussian elimination after n equations. Now add a small error to each answer: b = a . s + e mod q, where e is a few units at most. Elimination fails, because combining equations multiplies and adds the errors until they cover the whole range. Recovering s from these noisy equations is the learning with errors (LWE) problem, introduced by Regev in 2005. The best known classical and quantum attacks are lattice reduction algorithms whose cost grows exponentially in n. Regev also showed that an efficient LWE solver would yield a quantum algorithm for worst-case lattice problems, which gives it a foundation that RSA-style assumptions lack.

Encrypting one bit with LWE is a direct consequence. The public key is a matrix A and the vector t = A s + e. To encrypt, pick a small random r and send u = A^T r + e1 and v = t . r + e2 + bit x round(q/2). The holder of s computes v - s . u. Everything cancels except bit x round(q/2) plus a combination of small errors: e . r + e2 - s . e1. If that combination stays below q/4 in absolute value, rounding to the nearer of 0 or q/2 recovers the bit. The noise that makes the problem hard is the same noise that can make decryption fail, so every parameter set is a negotiated margin between the two.

Learning with errors

Take a secret vector s of length n with entries mod q. If I give you many pairs (a, a . s mod q) with random a, you recover s by Gaussian elimination after n equations. Now add a small error to each answer: b = a . s + e mod q, where e is a few units at most. Elimination fails, because combining equations multiplies and adds the errors until they cover the whole range. Recovering s from these noisy equations is the learning with errors (LWE) problem, introduced by Regev in 2005. The best known classical and quantum attacks are lattice reduction algorithms whose cost grows exponentially in n. Regev also showed that an efficient LWE solver would yield a quantum algorithm for worst-case lattice problems, which gives it a foundation that RSA-style assumptions lack.

Encrypting one bit with LWE is a direct consequence. The public key is a matrix A and the vector t = A s + e. To encrypt, pick a small random r and send u = A^T r + e1 and v = t . r + e2 + bit x round(q/2). The holder of s computes v - s . u. Everything cancels except bit x round(q/2) plus a combination of small errors: e . r + e2 - s . e1. If that combination stays below q/4 in absolute value, rounding to the nearer of 0 or q/2 recovers the bit. The noise that makes the problem hard is the same noise that can make decryption fail, so every parameter set is a negotiated margin between the two.

From LWE to Module-LWE

Plain LWE needs an n x n matrix in the public key, which is hundreds of kilobytes at secure sizes. The fix is structure. Replace numbers with polynomials in the ring R_q = Z_q[X]/(Xⁿ + 1), where Xⁿ wraps around to -1, and one ring element stands in for a whole n x n block. With n = 256, one ring element plays the part of a 256 x 256 negacyclic matrix but is stored as 256 coefficients. Module-LWE uses a small k x k matrix of such polynomials, so security can be tuned by changing k while the arithmetic stays the same. ML-KEM fixes n = 256 and q = 3329 for all three parameter sets and varies k, the noise widths and the compression. Because 256 divides q - 1 = 3328, the field has 256th roots of unity and multiplication can use a number-theoretic transform. ML-KEM's version stops one layer early and multiplies pairs of degree-one polynomials, since no 512th root exists; the general technique is in the NTT article, which covers the negacyclic case.

Noise is drawn from a centred binomial distribution: sum eta coin flips, subtract another eta. It is cheap to sample in constant time and gives values in [-eta, eta]. Ciphertexts are then compressed: each coefficient of u is rounded to du bits and each of v to dv bits. This shrinks the ciphertext and adds a little more rounding noise, which the margin must absorb.

The ML-KEM parameter sets

All three share n = 256 and q = 3329 and produce a 32-byte shared secret (FIPS 203, Tables 2 and 3). For comparison, an X25519 public key is 32 bytes. ML-KEM-768 is the common default and is the KEM inside the hybrid X25519MLKEM768 group now used in TLS 1.3.

A toy K-PKE in Python

The following is the CPA-secure encryption core, called K-PKE in FIPS 203, with ML-KEM-768's shape. It is a teaching model: it multiplies polynomials by convolution instead of the NTT, draws A directly instead of expanding it from a seed, and skips byte encoding and hashing. Do not use it to protect anything.

import numpy as np

N, Q, K = 256, 3329, 3                 # ML-KEM-768 shape
ETA1, ETA2, DU, DV = 2, 2, 10, 4
rng = np.random.default_rng()          # toy only: not a CSPRNG

def polymul(a, b):
    """Multiply in Z_q[X]/(X^N + 1): X^N wraps to -1 (negacyclic)."""
    full = np.convolve(a, b)
    res = full[:N].copy()
    res[: len(full) - N] -= full[N:]
    return res % Q

def cbd(eta, shape):                   # centred binomial noise in [-eta, eta]
    bits = rng.integers(0, 2, size=shape + (2 * eta,))
    return bits[..., :eta].sum(-1) - bits[..., eta:].sum(-1)

def matvec(M, v):
    return np.array([sum(polymul(M[i][j], v[j]) for j in range(K)) % Q
                     for i in range(K)])

def compress(x, d):
    return np.floor(x * 2**d / Q + 0.5).astype(np.int64) % 2**d

def decompress(y, d):
    return np.floor(y * Q / 2**d + 0.5).astype(np.int64)

def keygen():
    A = rng.integers(0, Q, size=(K, K, N))
    s, e = cbd(ETA1, (K, N)), cbd(ETA1, (K, N))
    return (A, (matvec(A, s) + e) % Q), s

def encrypt(pk, m):                    # m: 256 bits as 0/1 array
    A, t = pk
    r, e1, e2 = cbd(ETA1, (K, N)), cbd(ETA2, (K, N)), cbd(ETA2, (N,))
    u = (matvec(A.transpose(1, 0, 2), r) + e1) % Q
    v = (sum(polymul(t[i], r[i]) for i in range(K)) + e2 + m * ((Q + 1) // 2)) % Q
    return compress(u, DU), compress(v, DV)

def decrypt(s, ct):
    u, v = decompress(ct[0], DU), decompress(ct[1], DV)
    w = (v - sum(polymul(s[i], u[i]) for i in range(K))) % Q
    return compress(w, 1)              # nearer q/2 -> 1, nearer 0 -> 0

Worked example: measuring the noise budget

Run keygen, encrypt a random 256-bit message and decrypt it, 300 times. Every message came back intact. To see how much margin was left, subtract the encoded message from w and centre each coefficient into [-1664, 1664]. Across all 300 runs and all 256 coefficients, the largest noise magnitude measured was 294. The decision threshold is q/4, about 832, so the worst case observed used roughly a third of the margin. That is the picture behind the standard's claim of negligible failure: the noise is a sum of many small, nearly independent products, so it concentrates tightly and the tail beyond 832 is astronomically thin.

You can watch the dial turn. In 100-message runs, ETA1 = 8 still decrypted everything, ETA1 = 12 garbled 2 messages and ETA1 = 16 garbled 29. Dropping DV to 1, so that compression alone can move v by q/4, corrupted 595 of 25,600 bits. Lower the noise to zero and decryption is perfect, but t = A s is then a plain linear system and the secret falls to elimination in microseconds.

From K-PKE to ML-KEM

K-PKE is only secure against passive attackers. An active attacker who submits crafted ciphertexts and watches whether decryption fails can learn s bit by bit, because failures depend on the secret. ML-KEM wraps K-PKE in a variant of the Fujisaki-Okamoto transform. Encapsulation picks a random 32-byte m, derives both the shared key K and the encryption randomness from m and a hash of the public key, and encrypts m deterministically with that randomness. Decapsulation decrypts to m', re-derives the randomness, re-encrypts, and compares with the received ciphertext. If they differ it returns a pseudorandom key derived from a secret value z and the ciphertext instead of an error. This implicit rejection means an attacker never learns that a ciphertext was malformed; the two sides simply disagree on the key.

Two more differences separate the toy from the standard. The matrix A is expanded from a 32-byte seed with SHAKE128, so the public key carries the seed instead of k x k x 256 coefficients. All multiplication happens in the NTT domain, where it is pointwise. ML-DSA uses the same ring structure for signatures. It pairs Module-LWE with a related problem, Module-SIS, and uses a Fiat-Shamir construction that rejects and retries any signature that would leak information about the key.

Operational guidance

• Deploy hybrid first. Combine ML-KEM with X25519 so the session is safe if either holds. Lattice schemes are younger than elliptic curves, and hybrids cost only a few kilobytes per handshake.
• Use a vetted, constant-time library. Prefer an implementation with a FIPS 203 validation or a well-reviewed open-source codebase. The KyberSlash timing issues found in 2023 and 2024 came from secret-dependent division in otherwise careful implementations.
• Watch packet sizes. An ML-KEM-768 key share is 1,184 bytes, so a hybrid ClientHello can exceed one TCP segment. Middleboxes that assume a single-packet ClientHello have broken real connections; test your path.
• Validate inputs. FIPS 203 requires checks on encapsulation keys, such as confirming the encoded coefficients are reduced mod q. Skipping them turns malformed keys into undefined behaviour.
• Never reuse encryption randomness. The FO transform derives it from fresh m; a broken RNG that repeats m repeats the shared key.

Failure modes

• Secret-dependent timing. Divisions, early-exit comparisons and table lookups indexed by secrets leak through timing and cache. The re-encryption comparison in decapsulation must be constant time.
• Fault attacks. On embedded devices, a glitch that skips the re-encryption check removes the CCA protection; hardened builds verify twice.
• Rolling your own parameters. Shrinking n or q to save bytes moves you off the analysed security estimates. Use only the three standard sets.
• Confusing PKE with KEM. Exposing K-PKE decryption directly, without the transform, enables key-recovery through failure oracles.
• Mixing up encodings. Pre-standard Kyber round-3 and final ML-KEM differ in details of key derivation and are not interoperable; label which one an endpoint speaks.

Trade-offs

What to do next

1. Run the toy code, then change ETA1 and DV and plot the noise histogram against the 832 threshold to see how parameters set the failure rate.
2. Read FIPS 203 sections 5 and 6 side by side with the toy and list each step the toy skips.
3. Check whether your TLS stack offers X25519MLKEM768 and enable it on a staging endpoint; capture a handshake to see the key-share sizes.
4. Work through the NTT so the real implementation's multiplication is no longer a black box.
5. For long-lived signatures such as firmware, compare ML-DSA with hash-based signatures.
6. Add every RSA and ECC use you find to the inventory described in the migration guide, ranked by how long the data must stay secret.