Skip to main content

📊 Dots on Paper

Learning About Lattices​

🎯 The Simple Story​

Imagine you have a piece of paper with dots arranged in a perfect grid:

• • • • • • •
• • • • • • •
• • • • • • •
• • • • • • •

Every dot is like a "home base" you can jump from!

Question: Can you get from any dot to any other dot using only these movements?

  • Jump 1 unit right or left
  • Jump 1 unit up or down

Answer: YES! Every dot is reachable!

This pattern of dots is called a lattice - and it's the secret sauce of ML-KEM's security!

🧠 Mental Model​

Hold this picture in your head:

Imagine the lattice as a giant fishing net:

     /\       /\
    /  \_____/  \
   /    \    /    \
  /______\  /______\

Pattern at every corner: Same shape repeats!

All corners = "lattice points"

Key ideas:

  1. Regular pattern: Every gap is the same size
  2. Infinite: The pattern repeats forever
  3. Jump rules: Specific ways to move from point to point

Another way to think:

  • Like graph paper - the grid itself
  • Like a tiled floor - same tile pattern everywhere
  • Like city blocks - same streets, identical blocks

📊 See It Happen​

Let's see how you move around a lattice:

🎮 Try It Yourself​

Question 1: You start at the origin (0, 0) on the lattice. You follow vector (5, 3). Where do you land?

Show Answer

Starting: (0, 0)

Vector (5, 3) means: 5 right, 3 down

So: 0 + 5 = 5 for the first coordinate 0 + 3 = 3 for the second coordinate

Answer: (5, 3) - which is definitely a lattice point!

Question 2: If you're at (2, 2) and follow vector (1, -1), where do you end up?

Show Answer

Current position: (2, 2)

Vector (1, -1) means: 1 right, 1 down

Add the vector: (2, 2) + (1, -1) = (3, 1)

Answer: (3, 1) - another lattice point!

Question 3: What vectors can you use to get from the origin to (4, 6)?

Show Answer

Think of it backwards: To get from (0, 0) to (4, 6), you need to move 4 right, 6 up.

So ANY vector that adds up to (4, 6) works!

Examples:

  • (4, 6) = one jump of 4 right, 6 up
  • (2, 3) + (2, 3) = two jumps of 2 right, 3 up each
  • (1, 1) + (3, 5) = two different jumps
  • (0, 0) + (4, 6) = nothing then one big jump (trivial!)
  • (10, 10) + (-6, -4) = overshoot then come back (still works!)

All of these get you to (4, 6)!

🔢 The Math​

What Is a Lattice?​

A lattice is a set of points defined by integer combinations of basis vectors:

L={n1b1+n2b2+⋯+nkbk∣ni∈Z}L = \{ n_1 \mathbf{b}_1 + n_2 \mathbf{b}_2 + \dots + n_k \mathbf{b}_k \mid n_i \in \mathbb{Z} \}

In simpler terms:

  • b1,b2,…\mathbf{b}_1, \mathbf{b}_2, \dots = basis vectors (jump rules)
  • n1,n2,…n_1, n_2, \dots = integers (how many times to jump)
  • Any point = combination of jumping on the basis vectors

Example 2D lattice:

Basis vectors: b1=(1,0)\mathbf{b}_1 = (1, 0), b2=(0,1)\mathbf{b}_2 = (0, 1)

Lattice points:

  • 0b1+0b2=(0,0)0\mathbf{b}_1 + 0\mathbf{b}_2 = (0, 0)
  • 1b1+0b2=(1,0)1\mathbf{b}_1 + 0\mathbf{b}_2 = (1, 0)
  • 0b1+1b2=(0,1)0\mathbf{b}_1 + 1\mathbf{b}_2 = (0, 1)
  • 3b1+2b2=(3,2)3\mathbf{b}_1 + 2\mathbf{b}_2 = (3, 2)
  • etc.

Basis Vectors​

Simplest 2D lattice: b1=(1,0),b2=(0,1)\mathbf{b}_1 = (1, 0), \mathbf{b}_2 = (0, 1)

This creates the standard grid:

• • • • •  ← y = 1 (0,1) + (1,0)(n)
  ↓  ↓  ↓
  =  = =   ← y = 0 (0,0) + (1,0)(n)
  0  1  2  → x axis

Rotated lattice: b1=(2,1),b2=(1,2)\mathbf{b}_1 = (2, 1), \mathbf{b}_2 = (1, 2)

Still a lattice, but the grid is tilted!

High-Dimensional Lattices​

ML-KEM uses a 256-dimensional lattice!

L={n1b1+⋯+n256b256∣ni∈Z}L = \{ n_1 \mathbf{b}_1 + \dots + n_{256} \mathbf{b}_{256} \mid n_i \in \mathbb{Z} \}

Each point has 256 coordinates!

💡 Why We Care​

The Shortest Vector Problem (SVP)​

Here's the hard problem ML-KEM relies on:

Question: Given a lattice, find the shortest vector (closest arrow to the origin)?

Easy if 2D:

  • Look at the lattice
  • Measure distances
  • Pick the shortest

Impossible in 256D:

  • Too many points!
  • Can't visualize
  • No efficient algorithm known

This is a believed-hard problem! Classical and quantum computers can't solve it efficiently (so far!)

ML-KEM's Security Reduction​

The beautiful thing: ML-KEM's security is proven to be as hard as SVP!

This is called a security reduction - if you solve an "easy" problem (MLWE), you've solved a "hard" problem (SVP)!

Lattices and ML-KEM​

ML-KEM doesn't use all of lattice theory - it uses this simplified version:

The vectors in ML-KEM are lattice vectors

t=As+e\mathbf{t} = \mathbf{A}\mathbf{s} + \mathbf{e}

  • As\mathbf{A}\mathbf{s} = A lattice vector
  • e\mathbf{e} = Small noise (fog)
  • t\mathbf{t} = The noisy result (noisy lattice vector)

The attacker sees t\mathbf{t} (noisy) but wants s\mathbf{s} (clean). This is exactly like: "Find the nearest lattice point" = SVP = Hard!

✅ Quick Check​

Can you explain lattices to a 5-year-old?

Try saying this out loud:

"A lattice is like a pattern of dots on graph paper where every dot is a 'home base.' You can jump from any dot to any other dot using special jump rules. The pattern repeats forever in every direction!"

Can you find SVP on a small lattice?

Try this challenge:

Given these lattice points:

  • (0, 0)
  • (1, 0)
  • (0, 1)
  • (1, 1)
  • (2, 0)

Which vector to the origin is shortest?

Answer: Each point has a vector pointing back to (0, 0)

  • (1, 0) → back is (-1, 0) = length 1
  • (0, 1) → back is (0, -1) = length 1
  • (2, 0) → back is (-2, 0) = length 2

Shortest vectors are (1, 0) and (0, 1) (tie!)

🎓 Key Takeaways​

✅ Lattice = Grid of points following specific jump rules ✅ Basis vectors = Define how you can jump around ✅ Any point = Integer combination of basis vectors ✅ ML-KEM = Uses 256D lattices with polynomials ✅ SVP = Shortest Vector Problem (hard) ✅ Security = ML-KEM security reduces to SVP hardness

🎉 What You'll Learn Next​

Now you understand lattices! Next, we'll learn about:

📋 Instruction Grids → Matrices

How tables of arrows make operations faster and more compact!