Lattices Crypto : Mathematical Foundations

1.1 Introduction to Lattices (格子)

What is a lattice? Think of a lattice as an infinite grid of points in space. Imagine the integer coordinate points in 2D: (0,0), (1,0), (0,1), (1,1), etc. That's the simplest lattice! But lattices can be "tilted" or exist in higher dimensions.

📌 Mini Example: The set of all points (a, b) where a and b are integers forms a lattice: {..., (−1,2), (0,0), (1,3), (2,−1), ...}

1.1.1 Lattices and Bases

A basis is like the "building blocks" of your lattice. Just as you can describe any point on a grid using x and y coordinates, you can describe any lattice point using a basis.

📌 Mini Example:

  • Basis vectors: v₁ = (1, 0) and v₂ = (0, 1)
  • Any lattice point = a·v₁ + b·v₂ where a, b are integers
  • Point (3, 2) = 3·(1,0) + 2·(0,1)

1.1.2 Properties of Lattices

Here you'll learn what makes lattices special - they're closed under addition, they're discrete (points don't pile up), etc.

📌 Mini Example:

  • Closed under addition: If (2,3) and (1,−1) are in the lattice, then (2,3) + (1,−1) = (3,2) is also in the lattice ✓
  • Discrete: There's a minimum distance between points (no points infinitely close together)

1.1.3 Sublattices (部分格子)

Just like subgroups in group theory, these are lattices within lattices.

📌 Mini Example:

  • Original lattice: all integer points (a, b)
  • Sublattice: all even integer points (2a, 2b)
  • (2, 4), (0, 6), (−2, 8) are in the sublattice
  • (1, 3) is NOT in the sublattice

1.2 Gram-Schmidt Orthogonalization

This is a technique for taking your lattice basis vectors and creating an "orthogonal" version (perpendicular vectors). It's like taking a parallelogram grid and figuring out the equivalent rectangular grid.

📌 Mini Example:

  • Original basis: b₁ = (3, 0), b₂ = (1, 2)
  • After GSO: b₁* = (3, 0), b₂* = (0, 2)
  • The GSO vectors are perpendicular! b₁* ⊥ b₂*

1.2.2 GSO (Gram-Schmidt Orthogonalization)

This helps us understand how "skewed" our lattice is.

📌 Mini Example:

  • Bad basis (very skewed): b₁ = (100, 0), b₂ = (99, 1)
  • These are almost parallel! Hard to work with.
  • GSO reveals the true structure

1.3 Lattice Difficulty (格子の難解性)

This section introduces the idea that some lattices are "harder" than others - particularly relevant for cryptography!

📌 Mini Example:

  • Easy lattice: Integer grid - shortest vector is (1, 0) or (0, 1), length = 1
  • Hard lattice: High-dimensional lattice where finding the shortest vector requires checking billions of possibilities

1.4 Shortest Vector Problem (SVP)

The big question: Given a lattice, what's the shortest non-zero vector you can find? This is actually a computationally hard problem!

📌 Mini Example:

  • Lattice basis: b₁ = (5, 2), b₂ = (3, 7)
  • Candidate vectors: (5, 2) with length √29 ≈ 5.39
  • Or try: (5, 2) − (3, 7) = (2, −5) with length √29 ≈ 5.39
  • Or: 2·(3, 7) − 3·(5, 2) = (−9, 8) with length √145 ≈ 12.04
  • Finding the absolute shortest? That's the hard part!

1.4.2 Shortest Vector and Basis

The shortest vector might not be in your basis - you might need to combine basis vectors cleverly.

📌 Mini Example:

  • Basis: b₁ = (10, 0), b₂ = (0, 10)
  • Shortest non-zero vector in lattice: (10, 0) with length 10?
  • Actually, vectors like (10, 0), (0, 10), (10, 10) all have length ≥ 10
  • But with a different basis like v₁ = (1, 0), v₂ = (0, 1), we see shortest is length 1!

1.5 Minkowski's Theorem and Hermite's Constant

These are classical results about guaranteed properties of lattices.

📌 Mini Example for Minkowski:

  • Draw a circle of radius 2 centered at origin
  • Minkowski says: if the circle is big enough compared to the lattice "density," it MUST contain a lattice point (besides origin)
  • For integer lattice with area 1 per fundamental region, a circle of radius √2 guarantees a lattice point inside!

📌 Mini Example for Hermite:

  • 2D lattice with determinant (volume) = 1
  • Hermite's constant γ₂ = 2/√3 ≈ 1.15
  • Guarantees existence of non-zero vector with length ≤ √(2/√3) ≈ 1.07

1.5.3 Supplement: Existence in 4+ Dimensional Lattices

When we go beyond 3D, visualization becomes impossible, but the math still works! Minkowski's results extend to high dimensions.

📌 Mini Example:

  • 4D lattice: points like (a, b, c, d) where a, b, c, d are integers
  • A 4D "sphere" (hypersphere) of radius 2 in this lattice
  • Still guaranteed to contain non-zero lattice points!
  • Example point: (1, 1, 0, 0) has length √2 ≈ 1.41 < 2 ✓

1.6 Dual Lattices and Mordell's Inequality

The dual lattice is like a "frequency domain" version of your original lattice. If your lattice has very short vectors, the dual has long vectors, and vice versa!

📌 Mini Example:

  • Original lattice basis: b₁ = (2, 0), b₂ = (0, 3)
  • Dual lattice basis: b₁* = (1/2, 0), b₂* = (0, 1/3)
  • Notice: smaller spacing → larger dual spacing
  • Check: b₁ · b₂* = 2 · (1/2) = 1 ✓

1.6.1 Dual Lattice Properties

The dual lattice Λ* consists of all vectors y such that y · x is an integer for every x in the original lattice.

📌 Mini Example:

  • Original lattice: all (3a, 3b) for integers a, b
  • Test dual vector: y = (1/3, 0)
  • Check: (1/3, 0) · (3, 0) = 1 ✓
  • Check: (1/3, 0) · (0, 3) = 0 ✓
  • So y is in the dual lattice!

1.6.2 Mordell's Inequality

This gives a relationship between how "dense" a lattice is and how short its vectors can be.

📌 Mini Example:

  • 2D lattice with determinant (area) = 4
  • Mordell bounds the shortest vector length
  • Can't have both large determinant AND very short vectors
  • Trade-off: spreading out points ↔ having short connections

1.7 Introduction to Lattice Problems

Overview of computational problems that are central to lattice theory and cryptography.

📌 Mini Example: Three main problems:

  • SVP (Shortest Vector): Find the shortest non-zero vector
  • CVP (Closest Vector): Given point t not in lattice, find closest lattice point
  • BDD (Bounded Distance Decoding): CVP when we know t is close to lattice