02 — Lattices Made Simple

What Is a Lattice?

A lattice is a regular grid of points in space. Think of it as the pattern on graph paper, but in many dimensions.

2D Lattice (Visual)

    •     •     •     •     •
       \   |   /
        \  |  /   <- basis vectors
         \ | /
    •-----•-----•-----•-----•
         / | \
        /  |  \
    •     •     •     •     •

Every lattice point is a combination of integer multiples of the basis vectors.

In 2D: if basis vectors are b₁ = (2, 0) and b₂ = (1, 2), then every lattice point is:

• n × b₁ + m × b₂ for integers n, m
• Examples: (2,0), (1,2), (3,2), (0,4), (-1, -2), ...

Higher Dimensions

ML-KEM uses lattices in dimension 256 or 512. You can't visualise them, but the math works the same:

• Each point is defined by 256 or 512 coordinates
• The grid extends infinitely in all directions

The Hard Problem: Shortest Vector

Given a lattice (defined by its basis), find the shortest non-zero vector — the lattice point closest to the origin.

Why It's Hard

In 2D: Easy. You can see it.

In 3D: Still manageable with some work.

In 256D: Essentially impossible. The number of points to check grows exponentially with dimension.

The Approximate Version (Used in Crypto)

Cryptographers don't need the exact shortest vector — they use approximate versions:

• Shortest Vector Problem (SVP): Find a vector within some factor of the shortest
• Closest Vector Problem (CVP): Given a point near the lattice, find the nearest lattice point

Even the approximate versions are believed to be hard for both classical and quantum computers.

Why Lattices Are Good for Crypto

Property 1: One-Way Functions

With a "good" basis (short, nearly orthogonal vectors), lattice problems are easy. With a "bad" basis (long, skewed vectors), they're hard.

Trapdoor: The private key is the good basis. The public key is the bad basis.

Alice's private key (good basis):     Alice's public key (bad basis):
  short vectors                        long, messy vectors
      ↓                                    ↓
  "I can solve lattice problems"      "Nobody else can"

Property 2: Average-Case Hardness

Unlike factoring (where some numbers are easy to factor), lattice problems are hard on average — random instances are just as hard as worst-case instances. This means:

• No weak keys to accidentally generate
• Security doesn't depend on choosing special parameters

Property 3: Quantum Resistance

Shor's algorithm exploits periodicity in number theory:

• Factoring → periodic function (modular exponentiation)
• Discrete log → periodic function (elliptic curve points)

Lattices have no useful periodic structure for Shor's algorithm to find. The best quantum algorithm (Grover's) only gives a square-root speedup — insufficient to break practical parameters.

From Lattices to ML-KEM

ML-KEM doesn't directly use SVP or CVP. It uses a variant called Learning With Errors (LWE):

You're given many linear equations with a secret vector. But each equation has a small random error. Finding the secret is like solving a crossword where some clues are intentionally wrong.

See the next article: 03 — Learning With Errors.

Resources

• Regev, "On lattices, learning with errors, random linear codes, and cryptography" (2009), J. ACM 56(6). [Original LWE paper]
• Micciancio & Regev, "Lattice-based cryptography" (2009), Post-Quantum Cryptography, 147–191.