Les réseaux euclidiens (lattices)

Puisque Shor casse la factorisation et le logarithme discret, il faut fonder la cryptographie sur des problèmes différents, que même un ordinateur quantique ne sait pas résoudre efficacement. Les réseaux euclidiens (en anglais lattices) sont aujourd'hui les candidats les plus solides.

Qu'est-ce qu'un réseau euclidien ?

Un réseau est une grille régulière et infinie de points, engendrée par quelques vecteurs de base. À partir de deux vecteurs, on atteint tous les points obtenus en les additionnant un nombre entier de fois.

Réseau 2D engendré par v1 et v2

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

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

Les points forment un maillage parfaitement ordonné. Jusqu'ici, rien de difficile.

Le problème qui résiste

La difficulté apparaît quand on pose la bonne question :

• SVP (Shortest Vector Problem) : quel est le vecteur non nul le plus court du réseau ?
• CVP (Closest Vector Problem) : étant donné un point quelconque de l'espace, quel est le point du réseau le plus proche ?

En dimension 2, l'œil résout cela immédiatement. Mais les réseaux utilisés en cryptographie vivent en dimension 500, 1000 et au-delà. Là, l'intuition géométrique s'effondre : avec une base « mal choisie » (des vecteurs longs et presque parallèles), retrouver le point le plus proche devient un problème pour lequel aucun algorithme efficace n'est connu, ni classique ni quantique.

LWE : apprendre avec des erreurs

Le problème vedette est le LWE (Learning With Errors — apprentissage avec erreurs). L'idée : on donne un système d'équations linéaires, mais chaque équation est légèrement bruitée.

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

Sans bruit, un simple pivot de Gauss résout tout. Le petit bruit ajouté rend la récupération du secret aussi dure qu'un problème de réseau — donc hors de portée, y compris pour un ordinateur quantique.

Pourquoi c'est un bon fondement

Atout	Explication
Résistance quantique	aucun algorithme quantique efficace connu contre SVP/LWE
Efficacité	opérations rapides (additions, multiplications de vecteurs)
Polyvalence	permet chiffrement et signatures
Réductions	sécurité reliée à la dureté du pire cas du réseau

En résumé

Les réseaux euclidiens sont des grilles infinies de points engendrées par des vecteurs. Trouver le vecteur le plus court (SVP) ou le point le plus proche, ou résoudre l'apprentissage avec erreurs (LWE), devient infaisable en grande dimension, même quantiquement. Ces problèmes servent de fondation aux nouveaux systèmes post-quantiques.