Réseaux : fondements

Le NIST a publié le 13 août 2024 trois normes post-quantiques. Deux d'entre elles, FIPS 203 pour l'encapsulation de clé et FIPS 204 pour la signature, reposent sur le même objet mathématique — et cet objet n'est ni un entier à factoriser, ni un groupe où le logarithme discret serait difficile. C'est un réseau euclidien.

Ce chapitre installe l'objet, ses problèmes difficiles, et la seule chose qui décide de leur difficulté : la base dont on dispose pour le décrire. À la fin, vous aurez fait tourner deux fois le même algorithme d'attaque sur le même réseau, et obtenu deux réponses dont une seule est bonne.

Un réseau, c'est une grille engendrée

Soit $b_1, \dots, b_n$ des vecteurs linéairement indépendants de $\mathbb{R}^m$. Le réseau qu'ils engendrent est l'ensemble de leurs combinaisons à coefficients entiers :

Tout tient dans le $\mathbb{Z}$. Avec des coefficients réels, la même famille engendrerait un sous-espace vectoriel — un plan continu, où « le point le plus proche » n'a aucun sens puisque tous les points y sont. Avec des coefficients entiers, on obtient une grille de points isolés, et les questions de proximité redeviennent des questions.

Prenons un exemple qui servira tout le chapitre, dans le plan :

Quels points obtient-on ? Un point $(x, y) = a\,b_1 + b\,b_2$ vérifie $x = a + 2b$ et $y = 2a - b$, d'où $2x - y = 5b$ et $x + 2y = 5a$. Les deux coefficients $a$ et $b$ sont entiers exactement quand $x + 2y$ est multiple de 5. Ce réseau est donc

C'est un sous-ensemble de $\mathbb{Z}^2$ qui en retient un point sur cinq. Retenez ce chiffre 5, il va revenir.

Le même réseau, une infinité de bases

Un réseau n'a pas une base, il en a une infinité. Si $U$ est une matrice à coefficients entiers de déterminant $\pm 1$ — on la dit unimodulaire — alors $BU$ engendre exactement le même réseau que $B$. La condition sur le déterminant est ce qui rend $U^{-1}$ entière elle aussi : sans elle, on obtiendrait un sous-réseau plus grossier, pas le même réseau.

Appliquons-la à notre exemple, avec $U$ de déterminant $-1$ :

Les deux dernières colonnes disent l'essentiel. L'angle s'effondre — les vecteurs de la seconde base sont presque alignés — mais le déterminant ne bouge pas. C'est une propriété du réseau, pas de la base : géométriquement, c'est l'aire du parallélogramme construit sur les vecteurs de base, et cette aire vaut 5 dans les deux cas. Un point de réseau pour cinq unités d'aire, quelle que soit la manière de le décrire.

On note ce déterminant $\det(\mathcal{L})$, et il mesure la densité du réseau. Un petit déterminant, beaucoup de points ; un grand déterminant, des points clairsemés.

Trois problèmes, une seule difficulté

Sur un réseau, trois problèmes servent de fondation.

SVP (Shortest Vector Problem) : trouver le vecteur non nul le plus court. Sa longueur est notée $\lambda_1(\mathcal{L})$. Dans notre exemple, $\lambda_1 = \sqrt{5} \approx 2{,}24$.

CVP (Closest Vector Problem) : étant donné un point $t$ du plan qui n'est pas dans le réseau, trouver le point du réseau le plus proche. C'est le problème central du chapitre.

SIVP (Shortest Independent Vectors Problem) : trouver $n$ vecteurs indépendants tous courts. C'est la version dont Regev tire, au chapitre suivant, la réduction pire cas vers cas moyen de LWE.

Aucun de ces problèmes n'est utilisé sous sa forme exacte. La cryptographie emploie leurs versions approchées : trouver un vecteur au plus $\gamma$ fois plus long que l'optimum, avec $\gamma$ polynomial en $n$. Cette nuance mérite d'être dite franchement à des étudiants, car elle est souvent escamotée.

SVP exact est NP-difficile sous réductions randomisées, CVP exact est NP-difficile. Mais la sécurité des schémas à réseaux ne repose pas sur cette NP-difficulté. Pour $\gamma \geq \sqrt{n}$, le problème approché tombe dans $\mathsf{NP} \cap \mathsf{coNP}$ : il ne peut donc pas être NP-difficile sans effondrer la hiérarchie polynomiale. Ce sur quoi on s'appuie, c'est l'absence d'algorithme efficace connu — classique ou quantique — pour ces facteurs d'approximation, après quarante ans de tentatives. C'est une hypothèse solide, pas un théorème.

Une borne utile pour situer les ordres de grandeur : le théorème de Minkowski garantit $\lambda_1(\mathcal{L}) \leq \sqrt{n} \cdot \det(\mathcal{L})^{1/n}$. Ici, $\sqrt{2} \cdot \sqrt{5} \approx 3{,}16$, et le vrai $\lambda_1$ vaut 2,24 — la borne est respectée, et lâche. Pour les grandes dimensions on lui préfère l'heuristique gaussienne, $\lambda_1 \approx \sqrt{n / 2\pi e} \cdot \det(\mathcal{L})^{1/n}$, qui n'a de sens qu'asymptotiquement.

L'arrondi de Babai

Voici l'algorithme le plus simple qui attaque CVP. Il tient en trois lignes.

1Fonction Babai(B, t) : point du réseau2    c ← coordonnées de t dans la base B      // n nombres RÉELS3    Pour i de 1 à n Faire4        a[i] ← Arrondi(c[i])                 // n entiers5    FinPour6    Retourner a[1]·b[1] + … + a[n]·b[n]7FinFonction

On décompose la cible dans la base, on arrondit chaque coordonnée, on recombine. Le résultat est nécessairement un point du réseau, puisque ses coordonnées sont entières.

La lecture géométrique est plus parlante que le code. Arrondir toutes les coordonnées à l'entier le plus proche revient à demander : dans quelle cellule fondamentale la cible tombe-t-elle ? Or cette cellule est un parallélogramme dessiné par la base — un carré si la base est orthogonale, un fuseau très allongé si elle ne l'est pas. Une cellule presque carrée entoure son point ; un fuseau peut contenir un point qui en est très éloigné.

Déroulons les nombres pour la cible $t = (5{,}5\,;\,2{,}6)$, qui n'est pas dans le réseau.

Le même réseau, le même algorithme, la même cible, et un résultat 4,5 fois pire. Les deux points renvoyés appartiennent bien au réseau — $6 + 2\times2 = 10$ et $9 + 2\times3 = 15$ sont tous deux multiples de 5. Mais l'un est le plus proche et l'autre non.

Deux précisions d'honnêteté. D'abord, la base courte est ici exactement orthogonale — $(1,2) \cdot (2,-1) = 0$ — ce qui rend l'arrondi non seulement bon mais exact : le point renvoyé est le plus proche, et l'exercice ci-dessous le confirme par force brute. Une base seulement réduite, sans être orthogonale, donne un bon résultat, pas toujours l'optimal. Ensuite, l'écart n'est pas systématique : pour beaucoup de cibles, la base longue tombe juste par chance. Ce qui compte est qu'elle ne le garantit pas.

On tient là l'intuition de la trappe : le réseau est public, une base longue peut être publiée sans rien révéler, et la base courte du même réseau constitue le secret qui rend CVP facile. Attention toutefois — et c'est un point que la suite du cours corrigera — les schémas normalisés ne procèdent pas ainsi. GGH et NTRUSign publiaient littéralement une mauvaise base, et tous deux ont été cassés : les signatures fuyaient de l'information sur la base secrète. ML-KEM place son secret ailleurs, dans le bruit de LWE. L'intuition « même objet, deux descriptions, une seule utilisable » reste juste ; sa mise en œuvre naïve, non.

Réduire une base : Gauss, LLL, BKZ

Si une bonne base rend CVP facile, la question devient : peut-on fabriquer une bonne base à partir d'une mauvaise ? C'est le problème de la réduction, et c'est là que se joue réellement la sécurité.

En dimension 2, la réponse est oui, et l'algorithme est élémentaire. La réduction de Gauss (ou de Lagrange) répète deux opérations : garder le plus court des deux vecteurs en premier, puis raccourcir l'autre en lui retranchant le multiple entier du premier qui le rapproche le plus de l'origine, soit $b_2 \leftarrow b_2 - \lfloor \mu \rceil \, b_1$ avec $\mu = \langle b_1, b_2 \rangle / \|b_1\|^2$.

Sur notre base longue :

Deux tours suffisent : on retombe sur $(-2, 1)$ et $(1, 2)$, c'est-à-dire la base courte au signe et à l'ordre près. En dimension 2, une mauvaise base ne protège rien. La sécurité des réseaux ne vient pas du principe, elle vient de la dimension — ML-KEM-768 travaille sur 768 inconnues, et le réseau attaqué en compte davantage encore.

En dimension quelconque, l'algorithme de référence est LLL (Lenstra, Lenstra, Lovász, 1982). Il s'exécute en temps polynomial et garantit

Une garantie exponentielle en $n$ produite par un algorithme polynomial : en dimension 768, le facteur vaut $2^{384}$, ce qui ne garantit rien du tout. En pratique LLL fait beaucoup mieux que sa borne, et c'est cet écart entre la garantie prouvée et le comportement observé qui oblige toute l'estimation de sécurité à devenir expérimentale.

Pour mesurer ce comportement, on utilise le facteur de Hermite $\delta_0$, défini par

Plus $\delta_0$ est proche de 1, meilleure est la réduction. LLL plafonne autour de $\delta_0 \approx 1{,}02$ quelle que soit la dimension, et cela ne suffit pas à casser les schémas normalisés. D'où BKZ, qui généralise LLL : au lieu de travailler sur des paires de vecteurs, il résout SVP exactement sur des blocs de taille $\beta$ et propage. LLL est le cas $\beta = 2$. Augmenter $\beta$ améliore $\delta_0$ — au prix d'un oracle SVP en dimension $\beta$, dont le coût est exponentiel.

Estimer une sécurité qu'on ne sait pas prouver

Le modèle employé par les spécifications de ML-KEM et ML-DSA s'appelle core-SVP. Il compte le coût d'un seul appel à l'oracle SVP en dimension $\beta$, en ignorant délibérément le nombre d'appels et les facteurs polynomiaux. Les meilleurs cribles connus donnent $2^{0{,}292\beta}$ opérations en classique et $2^{0{,}265\beta}$ en quantique.

Attaquer ML-KEM-768 demande, d'après l'analyse publiée, un $\beta$ de l'ordre de 620, soit environ $2^{181}$ opérations classiques ; ML-KEM-1024 se situe vers $\beta = 873$. Ces chiffres sont des estimations dans un modèle de coût, pas des théorèmes, et il faut le dire aux étudiants sans détour. Le modèle core-SVP est conservateur sur un point — il n'attribue qu'un seul appel d'oracle là où l'attaque réelle en fait beaucoup — et optimiste sur un autre, puisqu'il ignore le coût mémoire du criblage, qui est colossal. Les niveaux de sécurité annoncés bougent quand la cryptanalyse progresse, et ils ont déjà bougé.

Deux remarques pour finir. La colonne quantique n'apporte qu'un gain marginal, 0,265 contre 0,292 : contrairement à Shor sur RSA, aucun effondrement n'est attendu ici, et c'est précisément pour cela que les réseaux ont été retenus. Et la dernière colonne explique le choix des jeux de paramètres : les niveaux 1, 3 et 5 du NIST se lisent directement sur ces exposants.

À vous

Le fil le plus formateur sur les réseaux est d'implémenter puis de casser. Complétez l'arrondi de Babai, puis regardez les deux bases répondre différemment à la même question. La force brute qui suit vérifie laquelle a raison — un luxe permis par la dimension 2, et la raison même pour laquelle les schémas réels travaillent en dimension plusieurs centaines.

// Deux bases du MÊME réseau : les points {(x, y) entiers | x + 2y ≡ 0 mod 5}.
const COURTE = { b1: [1, 2], b2: [2, -1] };   // orthogonale, vecteurs de norme √5
const LONGUE = { b1: [5, 0], b2: [8, 1] };    // presque alignés, 7,1° d'écart
const CIBLE = [5.5, 2.6];                     // pas un point du réseau

const det = (B) => B.b1[0] * B.b2[1] - B.b1[1] * B.b2[0];

// Coordonnées RÉELLES de t dans la base : t = c1·b1 + c2·b2.
function coordonnees(B, t) {
  const d = det(B);
  return [
    (t[0] * B.b2[1] - t[1] * B.b2[0]) / d,
    (B.b1[0] * t[1] - B.b1[1] * t[0]) / d,
  ];
}

const combiner = (B, c1, c2) => [
  c1 * B.b1[0] + c2 * B.b2[0],
  c1 * B.b1[1] + c2 * B.b2[1],
];

function babai(B, t) {
  const [c1, c2] = coordonnees(B, t);

  // À COMPLÉTER — un point du réseau a des coordonnées ENTIÈRES dans la base.
  // En l'état, la fonction renvoie la cible elle-même : distance nulle, mais
  // le « point » trouvé n'appartient pas au réseau.
  const a1 = c1;
  const a2 = c2;

  const point = combiner(B, a1, a2);
  return { c1, c2, a1, a2, point, d: Math.hypot(point[0] - t[0], point[1] - t[1]) };
}

// Un point est dans le réseau si ses coordonnées dans une base sont entières.
function dansLeReseau(p) {
  const [c1, c2] = coordonnees(COURTE, p);
  return Number.isInteger(Math.round(c1 * 1e9) / 1e9) &&
         Number.isInteger(Math.round(c2 * 1e9) / 1e9);
}

const n2 = (x) => x.toFixed(2);

for (const [nom, B] of [["courte", COURTE], ["longue", LONGUE]]) {
  const r = babai(B, CIBLE);
  console.log(
    `base ${nom.padEnd(7)} coords (${n2(r.c1)}, ${n2(r.c2)})` +
    ` → (${r.a1}, ${r.a2}) → point (${r.point}) ` +
    ` d = ${n2(r.d)}  dans le réseau : ${dansLeReseau(r.point)}`
  );
}

// Référence : le VRAI plus proche, cherché par force brute. Possible ici
// parce que la dimension est 2 ; c'est exactement ce qui devient hors de
// portée en dimension 768.
let meilleur = null;
for (let a = -20; a <= 20; a++) {
  for (let b = -20; b <= 20; b++) {
    const p = combiner(COURTE, a, b);
    const d = Math.hypot(p[0] - CIBLE[0], p[1] - CIBLE[1]);
    if (!meilleur || d < meilleur.d) meilleur = { p, d };
  }
}
console.log(`force brute   → point (${meilleur.p})   d = ${n2(meilleur.d)}`);

// Fourni : la réduction de Gauss, qui transforme une base du plan en la plus
// courte possible. Lancez-la sur LONGUE et regardez ce qu'elle rend.
function gauss(B) {
  let u = B.b1.slice();
  let v = B.b2.slice();
  const norme = (w) => Math.hypot(w[0], w[1]);
  for (let k = 0; k < 50; k++) {
    if (norme(u) > norme(v)) [u, v] = [v, u];
    const mu = Math.round((u[0] * v[0] + u[1] * v[1]) / (u[0] * u[0] + u[1] * u[1]));
    const w = [v[0] - mu * u[0], v[1] - mu * u[1]];
    if (norme(w) >= norme(u)) return { b1: u, b2: w };
    v = w;
  }
  return { b1: u, b2: v };
}
console.log("Gauss(LONGUE) =", JSON.stringify(gauss(LONGUE)));

const COURTE = { b1: [1, 2], b2: [2, -1] };
const LONGUE = { b1: [5, 0], b2: [8, 1] };
const CIBLE = [5.5, 2.6];

const det = (B) => B.b1[0] * B.b2[1] - B.b1[1] * B.b2[0];

function coordonnees(B, t) {
  const d = det(B);
  return [
    (t[0] * B.b2[1] - t[1] * B.b2[0]) / d,
    (B.b1[0] * t[1] - B.b1[1] * t[0]) / d,
  ];
}

const combiner = (B, c1, c2) => [
  c1 * B.b1[0] + c2 * B.b2[0],
  c1 * B.b1[1] + c2 * B.b2[1],
];

function babai(B, t) {
  const [c1, c2] = coordonnees(B, t);

  // L'arrondi, c'est TOUT l'algorithme. La difficulté du problème ne tient
  // pas à cette ligne mais à la base dans laquelle elle est appliquée.
  const a1 = Math.round(c1);
  const a2 = Math.round(c2);

  const point = combiner(B, a1, a2);
  return { c1, c2, a1, a2, point, d: Math.hypot(point[0] - t[0], point[1] - t[1]) };
}

function dansLeReseau(p) {
  const [c1, c2] = coordonnees(COURTE, p);
  return Number.isInteger(Math.round(c1 * 1e9) / 1e9) &&
         Number.isInteger(Math.round(c2 * 1e9) / 1e9);
}

const n2 = (x) => x.toFixed(2);

for (const [nom, B] of [["courte", COURTE], ["longue", LONGUE]]) {
  const r = babai(B, CIBLE);
  console.log(
    `base ${nom.padEnd(7)} coords (${n2(r.c1)}, ${n2(r.c2)})` +
    ` → (${r.a1}, ${r.a2}) → point (${r.point}) ` +
    ` d = ${n2(r.d)}  dans le réseau : ${dansLeReseau(r.point)}`
  );
}

let meilleur = null;
for (let a = -20; a <= 20; a++) {
  for (let b = -20; b <= 20; b++) {
    const p = combiner(COURTE, a, b);
    const d = Math.hypot(p[0] - CIBLE[0], p[1] - CIBLE[1]);
    if (!meilleur || d < meilleur.d) meilleur = { p, d };
  }
}
console.log(`force brute   → point (${meilleur.p})   d = ${n2(meilleur.d)}`);

function gauss(B) {
  let u = B.b1.slice();
  let v = B.b2.slice();
  const norme = (w) => Math.hypot(w[0], w[1]);
  for (let k = 0; k < 50; k++) {
    if (norme(u) > norme(v)) [u, v] = [v, u];
    const mu = Math.round((u[0] * v[0] + u[1] * v[1]) / (u[0] * u[0] + u[1] * u[1]));
    const w = [v[0] - mu * u[0], v[1] - mu * u[1]];
    if (norme(w) >= norme(u)) return { b1: u, b2: w };
    v = w;
  }
  return { b1: u, b2: v };
}
console.log("Gauss(LONGUE) =", JSON.stringify(gauss(LONGUE)));

// Trois choses à lire dans la sortie.
//
// 1. Les deux bases renvoient des points DIFFÉRENTS : (6, 2) à 0,78 de la
//    cible, (9, 3) à 3,52. Même réseau, même algorithme, même cible.
// 2. La force brute confirme (6, 2) : avec une base orthogonale, l'arrondi
//    ne se contente pas d'être bon, il est exact.
// 3. Gauss ramène LONGUE à { b1: [-2, 1], b2: [1, 2] }, soit COURTE au signe
//    et à l'ordre près. En dimension 2, la mauvaise base ne protège rien —
//    la sécurité vient de la dimension, pas du principe.

Ce que la suite en fait

Un réseau tel qu'il vient d'être décrit ne fait pas encore un cryptosystème : il manque le moyen d'engendrer, à la demande, une instance dont on connaît le secret sans que personne d'autre ne puisse le retrouver. C'est le rôle de LWE, au chapitre suivant, qui reformule tout ce chapitre en une seule phrase — résoudre un système linéaire bruité — et l'accompagne d'une réduction pire cas vers cas moyen que la géométrie seule ne fournissait pas.

Ce que vous emportez d'ici : le réseau est l'objet, la base est la description, et toute la construction repose sur l'écart entre les deux.

À retenir