Lattice Gentle — crypto-lab

What is a lattice?

Take two arrows and stamp a dot at every whole-number combination of them — that endless, perfectly regular grid of dots is a lattice. The same grid can be described by many different pairs of arrows, and here is the strange part: short, near-perpendicular arrows make the grid's secrets (its shortest dot, its nearest dot to any spot) easy to read off, while long, nearly-parallel arrows describe the identical grid and hide everything. That asymmetry is the guiding intuition of lattice-based cryptography — but hold it loosely: ML-KEM and ML-DSA never hand honest users a secret good basis. Their secrets are short vectors hidden inside noisy modular equations (Exhibits 4–5), and what the schemes stand on is the conjectured hardness of short-vector problems in high dimension, connected to MLWE and MSIS by security reductions.

① – ③ geometry: bases, SVP, CVP, LLL ④ the same gap over F_q: LWE & SIS ⑤ module versions: MLWE & MSIS ⇒ ML-KEM & ML-DSA

⚠ Not production crypto — a teaching demo with deliberately tiny parameters. It shows why the problems are believed hard; it does not prove hardness, and 2D lattices themselves are easy (Exhibit 3 solves them before your eyes — the hardness lives in dimension 500+).

Glossary — the eleven words this page leans on

Basis — the vectors whose integer combinations generate the lattice; many bases, one lattice.
Norm — a vector's length; the infinity norm is the largest absolute coordinate.
SVP — Shortest Vector Problem: find a shortest nonzero lattice point.
CVP — Closest Vector Problem: find the lattice point nearest a target.
BDD — CVP when the target is promised to be very close (LWE's situation).
LWE — Learning With Errors: recover s from noisy linear equations b = As + e mod q.
SIS — Short Integer Solutions: find a short nonzero z with Az = 0 mod q.
MLWE / MSIS — the same problems with polynomials in Z_q[x]/(xⁿ+1) as entries.
KEM — a scheme that transports a random shared key (not your message).
Signature — a scheme where only the key holder can produce values a public verifier accepts.

Sources: Menezes, A gentle introduction to lattice-based cryptography, eprint 2026/1098 (v1.1 — all numbered Examples cited below), and the cryptography101.ca Kyber/Dilithium slides (August 2024 — the V1/V2/V3 page citations). Every worked-example value on this page runs as a regression test against those sources.

Exhibit 1 · One lattice, many bases — and decoding by rounding

The dots are a fixed lattice (Example 2.24 of the notes). The arrows b₁, b₂ are a description of it — drag their tips (or type coordinates) and watch the status line prove, by exact integer arithmetic, whether your arrows still generate the same dots. The point t is a target: "decoding" rounds t's coordinates in your current basis to whole numbers — the Closest Vector Problem, solved the naive way. With the good basis the rounding error is small; switch to the bad basis of the same lattice and the same rounding lands far away. (Examples 2.7, 2.8, 2.10, 2.24 of the notes.)

Try first: press "Bad basis B′" — does the dot pattern change? Does the decode?

Next: if bases can hide the near points, can they hide the short ones too? That question has a name — SVP.

Exhibit 2 · Good basis, bad basis — the Shortest Vector Problem

The Shortest Vector Problem (SVP) asks: given a basis, find a shortest nonzero lattice point. Here the shortest vector is found by exhaustive search and highlighted; toggle between the two bases of Examples 2.7/2.8 and watch the answer stay put while its visibility changes completely.

Exact vs approximate — and where hardness really lives

Real cryptanalysis rarely needs an exactly-shortest vector: approx-SVP (find a vector at most γ times longer) is the working problem, and it only gets easier as γ grows. In two dimensions everything here is easy — Gauss's algorithm in Exhibit 3 solves SVP outright. The conjectured hardness that Kyber and Dilithium lean on appears when the dimension reaches the hundreds, where the best known algorithms (BKZ with sieving) run in time exponential in the dimension.

Next: if a bad basis is the obstacle, can we compute our way back to a good one? Sometimes — that is lattice reduction.

Exhibit 3 · Turning a bad basis good: Gauss and LLL, step by step

Reduction algorithms repair bad bases. Gauss's algorithm (2D) repeatedly subtracts the right whole-number multiple of the shorter vector from the longer one — watch ‖v‖ collapse. LLL generalizes exactly that subtraction to any dimension and adds one new idea, the Lovász condition, which decides when two neighbours should swap places. Every line below is replayed from the real algorithm's trace.

⚠ What this isn't: LLL at toy sizes, shown honestly. Attacking real 500-dimensional schemes needs BKZ and sieving at scale, which no browser demo can meaningfully show — this lab stops at the mechanism.

Next: cryptography cannot ship pictures of dots. The same geometry, rewritten as matrices mod q, is called LWE and SIS.

Exhibit 4 · The same gap, spoken in F_q: LWE and SIS

Cryptography can't ship pictures of dots; it ships matrices modulo q. Learning With Errors hides a secret behind noisy linear equations; Short Integer Solutions asks for a short kernel vector. Both are the geometry you just played with, re-coordinatized: LWE is CVP and SIS is SVP, in a lattice built from the matrix A (an exact formulation, §3–4 of the notes, not an analogy). Type candidates and both sides of each equation are computed for real. (Examples 4.3 and 3.2 of the notes.)

Next: swap the matrix entries for small polynomials and LWE/SIS become MLWE/MSIS — the exact problems under Kyber and Dilithium.

Exhibit 5 · Standing on the gap: toy-Kyber and toy-Dilithium

Kyber (ML-KEM, FIPS 203) and Dilithium (ML-DSA, FIPS 204) upgrade LWE and SIS to module versions — the same equations with polynomials in Z_q[x]/(x⁴+1) as the numbers. Notice what the secret is in both schemes: a short vector, never a good basis — an ML-KEM recipient does not possess one. Basis quality was the geometric lens of Exhibits 1–3; MLWE and MSIS are the exact problems, and the bridge from them to worst-case lattice problems is a security reduction, not a picture. Both demos below run the teaching slides' exact toy parameters, reproduce their worked examples digit for digit, and let you break things and watch the real arithmetic refuse.

Next: five questions. If you can answer them, you did not just watch this page — you learned it.

Check yourself · five questions, zero numbers to recall

Every question asks you to transfer an idea to a situation this page never showed — none asks you to remember a displayed value. Answer, then read why; wrong answers teach more than right ones here.

What's real here — and what isn't

Real: all lattice arithmetic (exact integers), Gauss and LLL reductions (instrumented, not animated from a script), all F_q and R_q arithmetic, the LWE/SIS instances and both toy schemes end to end, SHA-256 hashing (WebCrypto), rejection sampling, and every accept/reject decision on this page, including the KEM's implicit-rejection fallback path. All worked-example values match the notes and slides exactly — they run as worked-example regression tests (not official FIPS/ACVP vectors) in CI.
Simplified: toy parameter sizes (n = 4 instead of 256); SHA-256 standing in for SHAKE; Kyber shown without ciphertext compression and Dilithium without t-compression or hints, exactly as the teaching notes present them — each scheme panel carries a toy-vs-standard table listing every deviation.
Not proved: nothing here demonstrates that lattice problems are hard — 2D instances are easy by design. The demo shows why the hardness assumption has the shape it has, not that it holds.
Out of scope: full-parameter ML-KEM/ML-DSA (see crypto-lab-kyber-vault and crypto-lab-dilithium-seal), lattice attacks at scale — BKZ, sieving, nonce leaks (see crypto-lab-nonce-lattice), and non-lattice PQC families (see crypto-lab-pq-families).