Lab
Lattices: SVP, CVP, and the PQC trapdoor
Interactive 2D visualization of the shortest and closest vector problems, basis reduction, and GGH-style encryption that underpins lattice-based post-quantum cryptography.
Educational demo - don't copy/paste into production
What this is
ML-KEM and ML-DSA do not rest on factoring. They rest on lattice problems: finding the shortest vector in a grid of points, and the lattice point closest to a target. This playground makes both visible in 2D, then shows how the closest-vector problem becomes a one-way trapdoor.
The big idea
- One lattice has many bases. Good ones are short; bad ones are skewed.
- A good basis solves these problems. A bad one does not.
- The good basis is the private key. The bad basis is public.
Lattice
Mode
Drag the blue and pink arrowheads to reshape the lattice. Same dots, many bases.
Reading the picture
From these problems to post-quantum crypto
What is a lattice?
Pick two vectors. The lattice is every point you can reach by adding whole-number copies of them: a regular grid of dots. The same grid can be described by many different pairs of vectors. A good basis uses short, near-perpendicular vectors. A bad basis uses long, skewed ones. Drag the arrowheads in Bases mode and watch the dots stay put while the description changes.
Shortest Vector Problem (SVP)
Find the shortest nonzero vector in the lattice (the gold arrow). In 2D, Lagrange reduction solves this exactly and fast, which is what the Reduce button animates. In hundreds of dimensions the best known algorithm (LLL) only gets within a factor that grows exponentially with dimension. That gap is the security argument.
Closest Vector Problem (CVP)
Given a target that is not on the lattice, find the nearest dot. Babai's trick is to write the target in your basis and round each coordinate. With the good basis this lands on the closest dot. With the bad basis the rounding skews off and lands somewhere wrong. The good basis is the only practical way to solve CVP.
The trapdoor (GGH)
Encode a message as a lattice point, then add a small random error so the ciphertext sits just off the lattice. Decrypting means solving CVP. The holder of the good basis (the private key) rounds straight back to the message. An attacker with only the public bad basis rounds to the wrong point. This is the lattice analog of textbook RSA: perfect for intuition, not for production.
Why factoring falls and lattices stand
Shor breaks RSA and ECC
RSA's trapdoor is integer factorization: the modulus N = p·q is public, its prime factors are private. Shor's algorithm turns factoring into a periodicity problem a quantum computer extracts in polynomial time, collapsing RSA, Diffie-Hellman, and elliptic curves. That is the existential threat driving the migration.
Grover is a different, smaller threat
Grover's algorithm gives only a quadratic speedup for brute-force search. It does not break RSA's structure; it weakens symmetric ciphers and hashes by roughly halving their security level, which is why the fix is simply AES-256 and SHA-384. Against lattices it offers only modest help to sieving, not a break.
No hidden structure to exploit
Shor works because factoring hides an abelian group structure that the quantum Fourier transform exposes. SVP and CVP have no such structure. The best known quantum attacks stay exponential, which is why lattices are believed quantum-resistant and now anchor the NIST standards.
What the real algorithms use
ML-KEM does not use raw GGH. It uses Module-LWE, a randomized cousin where recovering the secret is a bounded-distance decoding problem, the same CVP geometry you are dragging here, lifted into high dimension over polynomial rings. ML-DSA uses related module-lattice assumptions for signatures.
Challenge 1: Many bases, one lattice
Do this: In Bases mode, click "Bad basis." The two arrows get long and skewed, but the dots are identical to the good basis.
Now: Click "Reduce." Watch the long basis shrink, step by step, back to a short near-orthogonal one while the dots never move.
Lagrange reduction is exact in 2D. The hardness only appears in high dimensions.
Challenge 2: Make the bad basis fail
Do this: Switch to Closest Vector mode on the Anisotropic lattice. Drag the red target around with "Round with good basis" selected: it always finds the green closest dot.
Now: Click "Round with bad basis" and drag again. Find a spot where the orange guess jumps to the wrong dot. That failure is the whole reason the bad basis is safe to publish.
Challenge 3: Be the attacker
Do this: In Encryption mode, set a message and click "Private key." Decryption recovers your exact message every time you draw a new error.
Now: Click "Attacker." With only the public bad basis, the recovered message is wrong. Try several errors and lattices.
Security model
Everything runs in your browser. No data leaves your device. All lattice math (basis reduction, Babai rounding, closest-vector search) runs locally in JavaScript. GGH here is a teaching model in 2D and is not secure; the standardized schemes use module-lattice problems in high dimension.