LWE et ses variantes

Le chapitre 4 a laissé une lacune, et il faut la nommer avant de la combler. Un réseau euclidien est un bel objet, mais rien n'y indique comment engendrer à la demande une instance difficile dont on connaît le secret. La trappe « base courte contre base longue » y ressemblait, mais nous avons vu que GGH et NTRUSign, qui la mettaient en œuvre littéralement, ont été cassés.

LWE répond exactement à cette question, et il le fait dans un langage que tout étudiant d'un cours d'algèbre linéaire comprend en une phrase.

Résoudre un système linéaire, mais bruité

Voici tout LWE en une image. On vous donne un système d'équations linéaires modulaires :

Vous le résolvez en trente secondes par élimination. Maintenant, on ajoute à chaque second membre une erreur de $\pm 1$ — une erreur minuscule, sur des valeurs comprises entre 0 et 16. Le système devient :

Appliquez la même élimination et regardez ce qui se passe.

Le résultat n'est pas « approximativement juste », il est absurde : $s_2 = 13$ au lieu de 1. La raison est visible à l'étape 5 de l'animation. Pour éliminer $s_1$, on a multiplié la seconde équation par 4 — et ce coefficient a multiplié son erreur par 4. Le bruit cumulé vaut 5, pas 1, dans un modulo de 17.

Généralisez à la dimension $n$ : éliminer $n-1$ inconnues demande des coefficients de l'ordre de $q$, et le bruit final dépasse $q/2$. Le résultat est alors uniformément distribué sur $\mathbb{Z}_q$ : il ne contient plus aucune information. C'est là toute l'astuce, et elle tient en une phrase — un bruit infime détruit toute méthode algébrique.

La définition, et sa version décisionnelle

Fixons le vocabulaire. Soient $n$ la dimension, $q$ le module et $\chi$ une distribution de bruit concentrée près de zéro. Un échantillon LWE de secret $s \in \mathbb{Z}_q^n$ est un couple

Le problème de recherche demande de retrouver $s$ à partir de $m$ échantillons. Le problème décisionnel demande seulement de distinguer une suite d'échantillons LWE d'une suite de couples uniformes. Ces deux problèmes sont équivalents pour les paramètres usuels, et c'est le décisionnel qui sert dans les preuves : il donne directement l'indistinguabilité dont les jeux IND-CPA ont besoin.

Deux paramètres gouvernent la difficulté : la dimension $n$ et le rapport bruit sur module $\alpha = \sigma / q$. Un bruit trop faible rend le problème facile ; un bruit trop fort rend le déchiffrement impossible. Tout le dimensionnement de ML-KEM tient dans cet équilibre.

La réduction de Regev

Voici ce qui distingue LWE de toutes les hypothèses classiques, et il faut l'énoncer précisément parce que c'est souvent déformé.

Regev a démontré en 2005 que résoudre LWE en moyenne est au moins aussi difficile que résoudre certains problèmes de réseau dans le pire cas — GapSVP et SIVP avec un facteur d'approximation $\tilde{O}(n/\alpha)$. La réduction originale est quantique ; Peikert en a donné en 2009 une version classique, au prix d'un module $q$ plus grand.

Ce que cela signifie, concrètement : si quelqu'un trouve un algorithme qui casse LWE sur des instances tirées au hasard — c'est-à-dire sur les clés que produit votre générateur — alors le même algorithme résout toutes les instances du problème de réseau correspondant, y compris les plus difficiles. Il n'existe donc pas de « clés faibles » à craindre : le tirage aléatoire ne peut pas tomber sur une instance accidentellement facile.

Comparez avec RSA. Personne ne sait montrer que factoriser un module tiré au hasard est aussi difficile que factoriser le pire module possible. On y croit ; on ne le démontre pas.

Deux réserves, pour rester honnête. D'abord, la réduction porte sur des facteurs d'approximation polynomiaux, pour lesquels le problème de réseau n'est ni prouvé NP-difficile ni supposé l'être — c'est la nuance du chapitre 4. Ensuite, elle est lâche : appliquée telle quelle, elle imposerait des paramètres bien plus gros que ceux de ML-KEM. Les paramètres réels sont fixés par l'estimation d'attaque du chapitre 4, pas par la réduction. Celle-ci sert de garantie structurelle, pas de règle de dimensionnement.

De LWE au réseau, et retour

La boucle se referme ici. À partir de $m$ échantillons $(A, b)$, on construit le réseau $q$-aire

Le vecteur $b$ est proche de ce réseau — à distance $\|e\|$, qui est petite. Résoudre LWE, c'est donc résoudre CVP sur $\Lambda$ avec la promesse que la cible est anormalement proche. L'attaque primale plonge le tout dans un réseau où le secret devient un vecteur unique et court, et lance BKZ ; l'attaque duale cherche des vecteurs courts du réseau orthogonal pour distinguer. Dans les deux cas, le coût est celui du chapitre 4 : $2^{0{,}292\beta}$.

Autrement dit, LWE n'est pas un nouveau problème difficile. C'est une présentation du problème de réseau qui rend l'engendrement d'instances trivial : tirer $A$ au hasard, tirer $s$ et $e$ petits, publier $(A, As+e)$.

Ring-LWE et Module-LWE : ce qu'on gagne, ce qu'on risque

LWE « plein » a un défaut rédhibitoire : la matrice $A$ fait $m \times n$ éléments. Pour des paramètres réalistes, la clé publique se compte en mégaoctets. C'est inutilisable.

Ring-LWE remplace les vecteurs par des éléments de l'anneau $R_q$ du chapitre 3. Un seul polynôme $a$ remplace toute une matrice, parce que la multiplication dans l'anneau encode implicitement une matrice circulante. On gagne un facteur $n$ en taille de clé et, grâce à la NTT, un facteur $n/\log n$ en temps de calcul. Le gain est spectaculaire.

Il n'est pas gratuit. Cette matrice implicite n'est pas quelconque : elle a une structure algébrique, et une structure est toujours une prise potentielle. On sait aujourd'hui que certains problèmes sur les réseaux idéaux — pas Ring-LWE lui-même, mais des cousins proches — admettent des algorithmes quantiques meilleurs que dans le cas général pour certains facteurs d'approximation. Ces résultats ne cassent pas Ring-LWE. Ils démontrent que la structure n'est pas neutre, et qu'elle mérite une prudence que le cas non structuré n'exige pas.

Module-LWE est le compromis, et c'est celui que le NIST a normalisé. On travaille avec des vecteurs de dimension $k$ dont les entrées sont des éléments de l'anneau. Pour $k = 1$ on retrouve Ring-LWE ; pour $k = n$ on retrouve LWE plein. ML-KEM prend $k = 2, 3$ ou $4$ avec $n = 256$.

Le bénéfice est double, et le second est le plus intéressant en pratique. D'une part, on réduit la structure algébrique en jouant sur $k$ plutôt que sur $n$. D'autre part, changer de niveau de sécurité ne change que $k$ : l'anneau reste le même, donc la NTT, les tables et le code d'arithmétique sont identiques pour les trois jeux de paramètres. Une implémentation, trois niveaux.

SIS, le problème dual

LWE sert au chiffrement. Les signatures ont besoin de son pendant, SIS — Short Integer Solution.

Étant donné $A \in \mathbb{Z}_q^{n \times m}$ uniforme, trouver $z \neq 0$ court tel que

Il existe une infinité de solutions dès que $m > n$ ; la difficulté est d'en trouver une petite. Ajtai a démontré dès 1996 la difficulté pire cas vers cas moyen de SIS, ce qui en fait historiquement la première construction de ce type.

L'intuition de la dualité : LWE cache un secret dans du bruit, SIS demande d'exhiber un objet court. Le chiffrement a besoin de cacher, la signature a besoin de prouver qu'on sait produire quelque chose de court sans révéler comment. Le chapitre 7 montre comment ML-DSA convertit cela en signature.

À vous

// LWE en miniature. q = 17, dimension n = 2, secret s = (3, 1).
// Bruit dans {-1, 0, +1}.

const q = 17;
const n = 2;
const SECRET = [3, 1];
const mod = (x) => ((x % q) + q) % q;

const produit = (a, s) => mod(a.reduce((t, ai, i) => t + ai * s[i], 0));

// Un échantillon LWE : (a, b) avec b = <a, s> + e.
function echantillon(bruit) {
  const a = Array.from({ length: n }, () => Math.floor(Math.random() * q));
  const e = bruit ? Math.floor(Math.random() * 3) - 1 : 0;
  return { a, b: mod(produit(a, SECRET) + e), e };
}

// Attaque par force brute : essayer tous les secrets, garder celui qui
// explique le mieux les échantillons.
function forceBrute(echantillons, borne) {
  let meilleur = null;
  let essais = 0;
  for (let s1 = 0; s1 < q; s1++) {
    for (let s2 = 0; s2 < q; s2++) {
      essais++;
      const s = [s1, s2];
      // À COMPLÉTER — comptez combien d'échantillons ce candidat explique,
      // c'est-à-dire pour lesquels |b - <a,s>| (centré sur 0) est ≤ borne.
      const score = 0;
      if (!meilleur || score > meilleur.score) meilleur = { s, score };
    }
  }
  return { ...meilleur, essais };
}

// Écart centré : dans Z_q, 16 est à distance 1 de 0, pas 16.
const ecart = (x) => Math.min(mod(x), q - mod(x));

const SANS = Array.from({ length: 8 }, () => echantillon(false));
const AVEC = Array.from({ length: 8 }, () => echantillon(true));

console.log("secret réel :", SECRET);
console.log("sans bruit  :", JSON.stringify(forceBrute(SANS, 0)));
console.log("avec bruit  :", JSON.stringify(forceBrute(AVEC, 1)));

// Le coût, maintenant. En dimension n, il y a q^n secrets possibles.
console.log("\ncoût de la force brute :");
for (const dim of [2, 4, 8, 256, 768]) {
  const bits = dim * Math.log2(q);
  console.log(`  n = ${String(dim).padStart(3)}  →  q^n = 2^${bits.toFixed(0)}`);
}

const q = 17;
const n = 2;
const SECRET = [3, 1];
const mod = (x) => ((x % q) + q) % q;

const produit = (a, s) => mod(a.reduce((t, ai, i) => t + ai * s[i], 0));

function echantillon(bruit) {
  const a = Array.from({ length: n }, () => Math.floor(Math.random() * q));
  const e = bruit ? Math.floor(Math.random() * 3) - 1 : 0;
  return { a, b: mod(produit(a, SECRET) + e), e };
}

const ecart = (x) => Math.min(mod(x), q - mod(x));

function forceBrute(echantillons, borne) {
  let meilleur = null;
  let essais = 0;
  for (let s1 = 0; s1 < q; s1++) {
    for (let s2 = 0; s2 < q; s2++) {
      essais++;
      const s = [s1, s2];
      // Un candidat est d'autant meilleur qu'il laisse un résidu PETIT sur
      // chaque échantillon. C'est la seule signature du bon secret : le
      // mauvais candidat produit des résidus uniformes sur tout Z_q.
      const score = echantillons.filter((ech) => ecart(ech.b - produit(ech.a, s)) <= borne).length;
      if (!meilleur || score > meilleur.score) meilleur = { s, score };
    }
  }
  return { ...meilleur, essais };
}

const SANS = Array.from({ length: 8 }, () => echantillon(false));
const AVEC = Array.from({ length: 8 }, () => echantillon(true));

console.log("secret réel :", SECRET);
console.log("sans bruit  :", JSON.stringify(forceBrute(SANS, 0)));
console.log("avec bruit  :", JSON.stringify(forceBrute(AVEC, 1)));

console.log("\ncoût de la force brute :");
for (const dim of [2, 4, 8, 256, 768]) {
  const bits = dim * Math.log2(q);
  console.log(`  n = ${String(dim).padStart(3)}  →  q^n = 2^${bits.toFixed(0)}`);
}

// Trois observations, dans l'ordre où elles comptent.
//
// 1. La force brute RETROUVE le secret, avec ou sans bruit. LWE n'est pas
//    difficile en dimension 2 — 289 candidats, c'est instantané. Le bruit
//    ne rend pas le problème insoluble, il supprime seulement les méthodes
//    ALGÉBRIQUES (l'élimination de Gauss de l'animation).
//
// 2. Le score du bon secret est 8/8 sans bruit, et 8/8 avec bruit si la
//    borne est bien choisie. Trop serrée, on rate le vrai secret ; trop
//    lâche, plusieurs candidats deviennent indistinguables. Le rapport
//    entre q et l'écart-type du bruit est LE paramètre de sécurité.
//
// 3. La dernière colonne est la vraie leçon. En dimension 768, il y a
//    2^3138 secrets possibles. La force brute est morte, l'élimination est
//    morte : il ne reste que la réduction de réseau du chapitre 4, avec le
//    coût exponentiel en β qu'on lui connaît.

À retenir