Lattices

Since Shor breaks factoring and the discrete logarithm, cryptography must be built on different problems that even a quantum computer cannot solve efficiently. Lattices (réseaux euclidiens in French) are today the strongest candidates.

What is a lattice?

A lattice is a regular and infinite grid of points, generated by a few basis vectors. Starting from two vectors, you reach every point obtained by adding them an integer number of times.

Réseau 2D engendré par v1 et v2

  .     .     .     .     .
     v2
  .   \ .     .     .     .
       \
  .     P-----> .     .     .
             v1
  .     .     .     .     .

Chaque point = a*v1 + b*v2  avec a, b entiers

The points form a perfectly ordered mesh. So far, nothing difficult.

The problem that resists

The difficulty appears when you ask the right question:

• SVP (Shortest Vector Problem): what is the shortest non-zero vector of the lattice?
• CVP (Closest Vector Problem): given an arbitrary point in space, what is the closest lattice point?

In dimension 2, the eye solves this instantly. But the lattices used in cryptography live in dimension 500, 1000 and beyond. There, geometric intuition collapses: with a "poorly chosen" basis (long, nearly parallel vectors), finding the closest point becomes a problem for which no efficient algorithm is known, classical or quantum.

LWE: learning with errors

The flagship problem is LWE (Learning With Errors). The idea: you are given a system of linear equations, but each equation is slightly noisy.

Sans bruit (facile) :        Avec bruit LWE (dur) :
3x + 5y = 8                  3x + 5y ≈ 8  (+ petite erreur)
2x + 7y = 11                 2x + 7y ≈ 11 (+ petite erreur)
-> résolu par élimination    -> l'erreur casse l'élimination

Without noise, a simple Gaussian pivot solves everything. The small added noise makes recovering the secret as hard as a lattice problem — thus out of reach, including for a quantum computer.

Why it is a good foundation

Strength	Explanation
Quantum resistance	no efficient quantum algorithm known against SVP/LWE
Efficiency	fast operations (additions, multiplications of vectors)
Versatility	supports encryption and signatures
Reductions	security tied to the worst-case hardness of the lattice

In summary

Lattices are infinite grids of points generated by vectors. Finding the shortest vector (SVP) or the closest point, or solving learning with errors (LWE), becomes infeasible in high dimension, even quantumly. These problems serve as the foundation of the new post-quantum systems.