Notebook 19 — ML-KEM parameters and the estimator

Notebook 19 — ML-KEM parameters and the estimator#

The closing chapter: we’ve seen our primal attack succeed on \(n \le 15\) in seconds. ML-KEM-512 has effective lattice dimension ~\(800\). This notebook explains why that gap translates to complete safety, using the community-standard lattice estimator.

Where ML-KEM’s numbers come from#

ML-KEM-512 parameters (FIPS 203):

\(n = 256\) (polynomial ring dimension)
\(k = 2\) (module rank)
\(q = 3329\)
\(\eta_1 = 3, \eta_2 = 2\) (CBD noise parameters)

The attack lattice for primal has dimension around \(n \cdot k + m = 256 \cdot 2 + 256 = 768\) (roughly). Running BKZ on this with \(\beta\) large enough to see a short enough vector is the threat model.

The lattice estimator#

Albrecht, Player, Scott (2015, extended through 2024) built a Python tool — lattice-estimator — that computes the expected cost of every known attack on a given LWE/MLWE instance: primal, dual, hybrid, BKW, and variants. NIST used it to pin down ML-KEM’s parameters.

A sample output for ML-KEM-512 (from the project’s published numbers):

Attack	\(\beta\)	Log cost
primal	400	143
dual	388	143
hybrid	411	141

Log cost 143 means roughly \(2^{143}\) operations — comparable to breaking AES-143 by brute force. The number for ML-KEM-1024 is \(\sim 2^{272}\).

Our toy numbers vs reality#

Instance	Lattice dim	\(\beta\) used	Python time	Log cost (estimator)
Our toy LWE, \(n = 10\)	31	4	~3 s	(below threshold)
Our toy LWE, \(n = 15\)	46	4	~10 s	~30
Our toy LWE, \(n = 25\)	76	~10 (infeasible pure-Py)	—	~55
ML-KEM-512	~768	400	—	143
ML-KEM-768	~1152	623	—	207
ML-KEM-1024	~1536	832	—	272

The jump from “feasible in seconds” to “infeasible at the heat-death of the universe” happens smoothly through \(\beta\) but is felt as a wall. It’s the same wall Part 4’s Shor analysis didn’t breach — classical and quantum, both ML-KEM parameters are safe today.

Why we trust these numbers#

The estimator accounts for all publicly known attacks as of 2024, including recent quantum sieve speedups.
NIST’s standardization process invited external cryptanalysis. Two rounds of candidate reductions (including Rainbow and SIKE being broken) established what “safe” looks like.
The 143-bit safety margin is above NIST’s “category 1” threshold (which roughly matches AES-128 security).
Hedging: we still use ML-KEM in hybrid with X25519. If someone finds a better lattice attack tomorrow, the classical half still protects the shared secret until Shor arrives.

How this connects back#

Part 1–4 built the scheme and walked through the positive case: here is how ML-KEM works.

Part 5 walked through the adversary’s side: here is how we’d attack it, and here’s how far we get on small parameters.

The combination — “we built it, we attacked it, we know where the walls are” — is what operational confidence in a cryptosystem looks like. In a few years, all TLS handshakes will be doing this math. You now know what’s happening inside.