v0.1 — interactive · toy lattice + Schnorr bridge · post-quantum, demystified

ML-KEM & ML-DSA, on a lattice

Both new NIST post-quantum standards live on the same mathematical object: a lattice. The hard problem isn't factoring or discrete logs (Shor's algorithm crushes both). It's finding short vectors in a high-dimensional grid riddled with deliberate noise. Build the intuition in 2D, encrypt a single bit Regev-style, then bridge to the real specs through a Schnorr signature.

/01

lattices and the LWE problem

post-quantum

// a lattice, geometrically

An infinite grid of points

Pick two vectors. Take every integer combination of them. That set of points is a lattice. A 2D lattice looks like graph paper if your vectors are nice and orthogonal, or a skewed mess if they're not.

Real ML-KEM uses lattices in 256+ dimensions. The math is identical; your intuition just stops working past about 4 dimensions.

// the hard problem

Closest vector, with noise

Given a target point off the lattice, finding the closest lattice point — the closest vector problem — is provably hard in high dimensions. There's no known classical or quantum algorithm that solves it efficiently.

That hardness is what every lattice-based cryptosystem rests on. ML-KEM hides a secret inside a noisy lattice point; only the key owner has the "shortcut" needed to recover it.

// basis // click anywhere on the grid to set a target

basis vector b₁

—

basis vector b₂

—

target point T

click on the grid

closest lattice point R

—

distance |T − R|

—

Both bases generate the exact same lattice — every integer combination of the orthogonal pair is also reachable by an integer combination of the skewed pair, and vice versa. The points on screen don't change when you toggle.

What changes is how easy the closest-vector search looks. With the orthogonal basis, you'd just round to the nearest grid line in each direction. With the skewed basis, the natural rounding gives you the wrong answer most of the time. A "good" basis is the secret key; a "bad" basis is what you publish. Anyone who only sees the bad basis is stuck doing CVP the hard way.

Now scale this up. In 256 dimensions there's no "obvious" rounding to try. The best known classical algorithm (BKZ, lattice basis reduction) runs in time exponential in the dimension. Even quantum computers only chip a small constant off the exponent — Shor's algorithm doesn't apply because lattices have no hidden subgroup structure.

// the LWE problem in dimension 4

parameters: n = 4, q = 17, error ∈ {−1, 0, 1}

The LWE equation: b = A·s + e (mod 17) DIM 4

A · s

+ noise e = → b =

// The LWE assumption: given (A, b), recovering s is hard for large n.
// Without noise, you'd just solve A⁻¹·b = s by linear algebra.
// The noise e is what makes this a one-way function.

// what's happening

Linear equations are easy. Add noise and they aren't.

Without the noise vector e, this would be a classical linear-algebra problem: invert the matrix A, multiply by b, recover s. A high-school student could do it.

But e is small random noise — each entry is in {−1, 0, +1}. That tiny perturbation breaks the linear-algebra approach completely. Now recovering s requires solving the Learning With Errors problem, which (for cryptographic parameter sizes) is provably as hard as worst-case lattice problems — including the closest vector problem you just played with above.

Notice: with n = 4 and q = 17 there are only 17⁴ = 83,521 possible s vectors. You could brute-force this by hand in an afternoon. ML-KEM uses n = 256 per polynomial and modulus q = 3329. The brute-force space is wider than the observable universe.

Switching the noise off is a button click; you'll see decryption becomes trivial. That's the whole point of the noise — it's the ingredient that makes the lattice problem cryptographic.

/02

encryption from LWE — Regev's trick

ML-KEM in miniature

Regev (2005) showed how to turn LWE into an encryption scheme. The construction is so direct it almost feels like cheating: the public key is just an LWE sample, and to encrypt a bit you mash a few of those samples together and add a half-of-q "kicker" if your bit is 1. To decrypt, you subtract off the secret part and check whether the leftover is closer to 0 or to q/2.

ML-KEM is a polished, polynomial-ring version of this. The mechanism you'll see below is the same one running in production TLS handshakes — just operating on tiny integers instead of 256-coefficient polynomials.

Bit to encrypt m = parameters: n = 4, m_samples = 4, q = 17

Public key (A, b) —

step 0 of 0

// what's happening at this step

Generating the keypair

Click Keygen to create a fresh keypair. The secret key is a small random vector s. The public key is a random matrix A together with a noisy product b = A·s + e.

Anyone seeing (A, b) can't recover s — that's the LWE assumption. But the matching private s can be used to cancel out the noise during decryption.

/03

from toys to ML-KEM

FIPS 203

Real ML-KEM does two things on top of toy LWE. First, it works over polynomials in R_q = ℤ_q[X] / (X²⁵⁶ + 1) — essentially, every "number" is replaced by a 256-coefficient polynomial. Multiplication uses the Number Theoretic Transform (NTT) for speed.

Second, ML-KEM is a key-encapsulation mechanism, not a general-purpose encryption scheme. Instead of encrypting your message directly, it encapsulates a fresh symmetric key. That key (32 bytes) then drives AES-GCM on the actual payload. The Fujisaki-Okamoto transform wraps the IND-CPA core into an IND-CCA-secure KEM.

ML-KEM-512

// AES-128 equivalent

module dimension k2

polynomial degree n256

modulus q3329

public key800 B

secret key1632 B

ciphertext768 B

shared secret32 B

ML-KEM-768

// AES-192 equivalent · most common

module dimension k3

polynomial degree n256

modulus q3329

public key1184 B

secret key2400 B

ciphertext1088 B

shared secret32 B

ML-KEM-1024

// AES-256 equivalent · CNSA 2.0

module dimension k4

polynomial degree n256

modulus q3329

public key1568 B

secret key3168 B

ciphertext1568 B

shared secret32 B

// translating the structure

The same shape, scaled up

Compare the toy Regev demo above to ML-KEM-768. In Regev: the secret is a 4-element integer vector. In ML-KEM: the secret is a 3-element polynomial vector, where each polynomial has 256 coefficients. That's 3 × 256 = 768 small integers — hence the name.

The encryption operation looks identical at the structural level: u = A^T·r + e₁ and v = b^T·r + e₂ + ⌊q/2⌋·m. Just with polynomial arithmetic instead of integer arithmetic, and the message m being a 256-bit packed value.

The Fujisaki-Okamoto transform is the box around all this that makes the scheme IND-CCA secure. It turns the KEM into a deterministic re-encryption check: the receiver re-encrypts the message they decrypt and rejects any ciphertext that doesn't match. This stops adaptive chosen-ciphertext attacks (the same family as Bleichenbacher's RSA padding-oracle attacks, but on the lattice side).

/04

signatures — Schnorr to ML-DSA

FIPS 204

ML-DSA's structure is easier to introduce through its classical ancestor — Schnorr signatures. Schnorr is a clean sigma-protocol: prover commits, verifier challenges, prover responds. Apply the Fiat-Shamir transform (use a hash function as the verifier) and you get a non-interactive signature.

ML-DSA does the exact same dance, but over a lattice. The complications it adds — rejection sampling and hint vectors — exist because lattices leak the secret through naive responses. Real ML-DSA is intricate; the structure is recognizable from Schnorr.

// toy Schnorr signature · group: ⟨g⟩ ⊂ ℤ*₂₃, order q = 11

Message m Nonce k (random)

Signer

// has private x

commitR = g^k mod p = —

challengec = H(m, R) mod q = —

responses = k + c·x mod q = —

signature—

Verifier

// has only public y, m, sig

recompute LHSg^s mod p = —

recompute RHSR · y^c mod p = —

match?—

// the structural bridge

From Schnorr to ML-DSA

Schnorr's signature is (R, s) where R = g^k commits the signer to a random nonce, and s = k + c·x reveals a key-dependent linear combination. The verifier checks g^s = R · y^c, which expands to g^k+cx = g^k · g^cx — true by exponent arithmetic when the signer knows x.

ML-DSA does the same thing on a lattice. Replace g^x with A·s (matrix-vector product over a polynomial ring), replace the response k + c·x with y + c·s where y is a random polynomial vector. Same algebraic shape; different math underneath.

The catch: in lattice land, leaking y + c·s directly would let an attacker recover s through enough samples (each y is small, so the response leaks information about s). ML-DSA's solution is rejection sampling: if the response would land in a region that leaks too much, the signer aborts and re-rolls the nonce. The signature is only emitted when it falls within a "safe" range. Hence the algorithm name in earlier drafts: "Dilithium signatures with aborts."

Two more tricks make real ML-DSA work: hint vectors compress the high bits of intermediate values for transmission; and the public key is a compressed form of A·s + e. The result is a signature ~3000 bytes long — much bigger than Ed25519's 64, but small enough to fit in a TLS handshake.

ML-DSA-44

// AES-128 equivalent

public key1312 B

secret key2560 B

signature2420 B

ML-DSA-65

// AES-192 equivalent

public key1952 B

secret key4032 B

signature3309 B

ML-DSA-87

// AES-256 equivalent · CNSA 2.0

public key2592 B

secret key4896 B

signature4627 B

/05

why quantum can't break it

Shor's algorithm needs a hidden subgroup. Lattices don't have one.

Shor's quantum algorithm — the one that breaks RSA and ECDH — works by reducing the problem to period-finding over an abelian group. The quantum Fourier transform reads off the period in polynomial time. Both factoring and discrete log have this structure; that's why both fall to the same attack.

Lattice problems don't. There's no hidden cyclic structure for the QFT to extract. The best known quantum algorithm for the shortest vector problem is Grover-amplified BKZ — which only shaves a constant factor off the exponent. ML-KEM-1024 and ML-DSA-87 are designed with that constant factor included; their claimed security is post-quantum, not just classical.

That doesn't mean lattices are provably safe forever. Quantum algorithm research is active. But it's the closest thing the cryptographic community has to a quantum-resistant foundation, and four NIST competition rounds (2017–2022) failed to find a break.

	Classical (RSA, ECDH)	Lattice (ML-KEM, ML-DSA)
Hard problem	Integer factoring · discrete logarithm	Module-LWE · Module-SIS · Closest Vector Problem
Best classical attack	NFS (sub-exponential)	BKZ basis reduction (exponential)
Best quantum attack	Shor (polynomial → broken)	Grover-improved BKZ (small constant speedup)
Public key size (≥128-bit security)	3072-bit RSA · 256-bit ECDH	800 B · 1184 B · 1568 B
Signature size	~256 B (ECDSA) · 384 B (RSA-3072)	2420 B · 3309 B · 4627 B
Speed	RSA decrypt slow · ECDH fast	All operations fast (microseconds in software)
Maturity	40+ years deployed	Standardized 2024 · field-tested in TLS hybrid since 2023

// post-quantum deployment timeline

2016

NIST opens the post-quantum competition. 69 submissions across KEMs and signatures.

2022

After 6 years and 3 rounds, NIST selects Kyber (KEM) and Dilithium, Falcon, SPHINCS+ (signatures).

2023

Cloudflare, Google Chrome, and AWS deploy X25519MLKEM768 hybrid key exchange in TLS. ~3% of TLS handshakes go post-quantum by year-end.

2024

FIPS 203 (ML-KEM) and FIPS 204 (ML-DSA) published. Apple announces PQ3 in iMessage. OpenSSH adopts ML-KEM hybrid by default.

2025

Hybrid PQ KEX becomes a majority of new TLS deployments. Signal Protocol moves to PQXDH (X25519 + ML-KEM).

2033

CNSA 2.0 deadline — U.S. national security systems must use ML-KEM-1024 and ML-DSA-87 (both AES-256-equivalent) for protection of classified data.

// the practical answer

Hybrid now, post-quantum later

The "harvest now, decrypt later" threat — record encrypted traffic today and decrypt it once you have a quantum computer — is what's driving the urgency. Anything you encrypt with X25519 alone in 2026 can be read in 2040 if a CRQC arrives by then.

Hybrid key exchange (classical AND post-quantum, both must be broken) is the bridge. If lattice cryptography turns out to have a flaw we missed, classical X25519 still protects the channel. If quantum computers arrive, ML-KEM still protects the channel. The cost is a slightly larger handshake (~1 KB extra).

The transition to post-quantum-only will probably take a decade more — until lattice cryptography has the same kind of decades-of-attacks track record that RSA and ECC have today. Until then, run both.