Skip to content

Lattices (gentle)

Prereqs: Modular arithmetic · Vectors and matrices · Hard problems
Next: Bridge: Noisy linear equations (LWE story) · Track: Lattice / LWE

Learning goals. Picture a lattice as a regular grid of points generated by vectors, see why “nearest lattice point” can be hard in high dimension, and connect that slogan to later LWE (noisy equations) without needing geometry class.

Why this page exists

NIST’s primary post-quantum KEM path (ML-KEM / Kyber-shaped schemes) is lattice-based.
The code-based track in this lab is still the densest curated paper path, but lattices deserve a full beginner ladder: grids → noisy equations → Module-LWE vocabulary.

This page is only the grid intuition. Take it slowly. Draw on paper.

Story first — street grid

Imagine a city with streets every block east–west and north–south.
Intersection points form a regular grid.

If you stand at a random GPS coordinate, “which intersection is closest?” is easy in 2D with your eyes.
In hundreds of dimensions, with a tilted grid, the same question can be computationally brutal — that hardness flavor is why lattices show up in crypto.

You do not need to visualize high dimensions. You need the habit: lattice = discrete points you can add; crypto puzzles hide near those points.

Part 1 — integer grid in 2D (the simplest lattice)

The set of all points with integer coordinates:

\[ \mathbb{Z}^2 = \{(x,y): x,y\text{ are integers}\}. \]

Examples of lattice points: \((0,0)\), \((1,0)\), \((0,1)\), \((-2,3)\), …

Non-examples: \((0.5, 0)\), \((\sqrt{2},1)\) — not on the integer grid.

Picture: graph paper dots.

Quick self-check

Is \((2,-1)\) on \(\mathbb{Z}^2\)? Is \((1,1/2)\)?

Answer Yes; no.

Part 2 — generated by basis vectors

A basis is a small set of vectors that generate the whole grid by integer combinations.

For the ordinary square grid, one basis is:

\[ \mathbf{b}_1=(1,0),\qquad \mathbf{b}_2=(0,1). \]

Any lattice point looks like:

\[ a_1\mathbf{b}_1 + a_2\mathbf{b}_2 \]

with integers \(a_1,a_2\). Example: \(3\mathbf{b}_1 + (-1)\mathbf{b}_2 = (3,-1)\).

A tilted basis (same grid, different description)

\[ \mathbf{b}_1'=(1,0),\qquad \mathbf{b}_2'=(1,1). \]

Integer mixes of \(\mathbf{b}_1',\mathbf{b}_2'\) still hit all of \(\mathbb{Z}^2\).
Moral: many bases can describe the same lattice. Crypto often hides a “nice” basis and publishes a “messy-looking” one.

Part 3 — nearest point (toy)

Target point \(\mathbf{t}=(1.2, 0.4)\) in the plane.
Nearest integer-grid point: \((1,0)\).

Distance feeling: a bit more than \(0.4\) away (you can sketch it).

Crypto slogan (CVP): given a lattice and a target, find a nearest lattice point.
Easy in tiny dimension with eyes; hard in high dimension for carefully chosen lattices.

You will not solve CVP on this page. You only need the English.

Part 4 — short vectors (toy)

Among nonzero lattice points of \(\mathbb{Z}^2\), the shortest have length \(1\) — like \((1,0)\).

Crypto slogan (SVP): find a shortest nonzero lattice vector.
Again: easy toy, hard in high dimension.

Part 5 — what this has to do with crypto (preview)

Lattice KEMs do not usually ask you to stare at a picture of a grid.
They ask you to work with noisy linear equations mod \(q\) whose secret is short / structured. Those problems are tightly connected to lattice problems.

Next bridge page: Noisy linear equations (LWE story).

Bridge to PQC

Later idea Lattice link
LWE Noisy modular equations; secret is short
Module-LWE Same idea with polynomial / module packaging (ML-KEM)
ML-KEM reading After LWE + Module-LWE concepts
Hardware papers (NTT, modmul) Fast arithmetic mod \(q\) for lattice schemes

Common confusions

  • Lattice ≠ “any random cloud of points” — it is a discrete additive grid.
  • You do not need multivariable calculus.
  • 2D pictures are metaphors; security lives in high dimension.
  • “Short” means small length / small coefficients — the secret’s special shape.
  • Code-based decoding and lattice LWE are different puzzles that share a “noise + linear algebra” vibe.

Check yourself

  1. Name three points of \(\mathbb{Z}^2\).
  2. In one sentence, what is a basis?
  3. What do CVP and SVP ask for, in English?
  4. True or false: every set of scattered points is a lattice.
Answers 1. e.g. $(0,0)$, $(2,5)$, $(-1,4)$. 2. A small set of vectors whose integer combinations make the whole lattice. 3. CVP: nearest lattice point to a target; SVP: shortest nonzero lattice vector. 4. False — lattices are regular discrete grids closed under addition.

Big practice set

  1. Write \((2,-1)\) as an integer combination of \((1,0)\) and \((0,1)\).
  2. Nearest \(\mathbb{Z}^2\) point to \((0.6, 0.6)\)? (Either \((1,1)\) or \((0,1)\) / \((1,0)\) — pick and justify by sketch.)
  3. Why might publishing a “messy” basis still define the same lattice as a “nice” basis?
Answers 1. $2\cdot(1,0)+(-1)\cdot(0,1)$. 2. $(1,1)$ is a natural choice (ties possible depending on exact distance — the point is the habit). 3. Different bases can generate the same set of points.

Next steps