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

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

ML-KEM est normalisé par la FIPS 203 et déployé aujourd'hui dans les navigateurs. C'est le schéma post-quantique que vos étudiants rencontreront le plus sûrement en production. Ce chapitre le construit brique par brique, en partant d'un objet que le chapitre précédent a rendu presque évident.

Un KEM, et pourquoi pas un chiffrement

Première clarification, souvent sautée. ML-KEM ne chiffre pas de messages. C'est un mécanisme d'encapsulation de clé — trois algorithmes :

Encaps ne prend aucun message en entrée. Elle produit une clé symétrique $K$ tirée au hasard et un chiffré $c$ qui permet au détenteur de $dk$ de la retrouver. On chiffre ensuite les vraies données avec $K$ et un AEAD.

Pourquoi cette forme plutôt qu'un chiffrement à clé publique ordinaire ? Parce qu'elle est plus simple à sécuriser. Un KEM n'a pas à gérer de bourrage, ni de messages de taille variable, ni de messages choisis par l'attaquant. Sa seule obligation est que $K$ soit indistinguable d'une clé aléatoire. En pratique, c'est aussi la seule chose dont les protocoles ont besoin : TLS, SSH et les autres veulent une clé de session, pas un chiffrement asymétrique de charge utile.

Le chiffrement sous-jacent

Sous ML-KEM se trouve un chiffrement à clé publique, appelé K-PKE, qui est du Module-LWE à peine déguisé.

Génération. Tirer $A$ pseudo-aléatoire de taille $k \times k$ sur $R_q$, et deux vecteurs courts $s$ et $e$. Publier $t = As + e$, garder $s$.

Chiffrement de $m$. Tirer $r$, $e_1$, $e_2$ courts, et calculer

Déchiffrement. Calculer $v - s^{T} u$ et arrondir chaque coefficient au multiple de $q/2$ le plus proche.

Le calcul décisif tient en deux lignes :

Le message est encodé en plaçant chaque bit soit près de 0, soit près de $q/2$. Le terme d'erreur est petit ; tant qu'il reste sous $q/4$, l'arrondi retombe sur le bon bit. Tout le dimensionnement de ML-KEM consiste à garder ce terme d'erreur sous $q/4$.

La compression, et le bruit qu'elle achète

Publier $u$ et $v$ avec 12 bits par coefficient donnerait des chiffrés inutilement gros. On les compresse en jetant des bits de poids faible :

La décompression rend une valeur approchée, à $q/2^{d+1}$ près. Cette erreur d'arrondi s'ajoute au budget de bruit — c'est pour cela que la compression n'est pas gratuite, et qu'on ne peut pas compresser autant qu'on voudrait.

Le point à faire remarquer en cours : $u$ et $v$ ne sont pas compressés au même taux. $u$ garde 10 ou 11 bits, $v$ seulement 4 ou 5. Ce n'est pas une inconséquence — $v$ ne transporte qu'un bit de message par coefficient, décodé en comparant à $q/2$, donc une erreur de cent unités y est sans conséquence. Chaque terme est compressé selon ce qu'il transporte.

De IND-CPA à IND-CCA2 : Fujisaki-Okamoto

Le K-PKE ci-dessus est IND-CPA, et seulement IND-CPA. Il est malléable : un attaquant qui modifie un chiffré valide obtient un chiffré qui se déchiffre encore, en un message différent mais lié. Contre un attaquant capable de soumettre des chiffrés au déchiffrement, c'est fatal.

La transformation de Fujisaki-Okamoto, dans sa variante avec rejet implicite, corrige cela avec une idée simple. On ré-encapsule :

1. déchiffrer $c$ pour obtenir $m'$ ;
2. dériver l'aléa $r'$ à partir de $m'$ lui-même — le chiffrement devient déterministe ;
3. rechiffrer $m'$ avec $r'$, obtenant $c'$ ;
4. si $c' = c$, renvoyer la clé ; sinon, renvoyer une clé bidon dérivée d'un secret interne.

Le test $c' = c$ prouve que $c$ a réellement été produit par la procédure d'encapsulation. Un chiffré fabriqué ne peut pas passer, puisque l'attaquant devrait deviner $m'$ à l'avance.

Le point délicat est la dernière ligne. On ne renvoie pas d'erreur : on renvoie une clé pseudo-aléatoire, fausse mais indistinguable d'une vraie. C'est le rejet implicite. Dire « échec » créerait un oracle : l'attaquant apprendrait quels chiffrés sont valides, et c'est exactement ce dont il a besoin. Le chapitre 11 en donne la preuve, et le chapitre 12 montre comment une implémentation bavarde rouvre l'oracle par le temps d'exécution.

Les trois jeux de paramètres

Notez ce que la table ne contient pas : ni $n$, ni $q$, ni l'anneau. Ils sont identiques pour les trois niveaux. Seul $k$ change, avec les taux de compression. C'est le bénéfice d'implémentation du Module-LWE annoncé au chapitre précédent.

Le taux d'échec de déchiffrement

ML-KEM peut échouer. C'est déroutant pour qui vient de RSA, et c'est structurel : si le terme de bruit dépasse $q/4$, un bit est mal décodé et la clé obtenue est fausse.

Les probabilités affichées ci-dessus — de l'ordre de $2^{-164}$ — rendent l'événement inobservable : il ne se produira jamais, sur aucun parc, pendant aucune durée. Mais elles ne sont pas nulles, et cela a deux conséquences qu'il faut énoncer.

D'abord, ce taux est un paramètre de sécurité, pas seulement de fiabilité. Un attaquant capable de provoquer des échecs, en soumettant des chiffrés spécialement construits, apprendrait de l'information sur le secret — chaque échec est une inégalité satisfaite par $s$. C'est l'attaque par échec de déchiffrement, et c'est pourquoi le taux doit être astronomiquement bas plutôt que simplement négligeable en pratique.

Ensuite, cela impose que la ré-encapsulation FO soit implémentée en temps constant, échec compris. Une implémentation qui met plus de temps sur un échec que sur un succès restaure exactement l'oracle qu'on cherchait à fermer.

À vous

// La compression de ML-KEM : jeter des bits de poids faible pour réduire
// le chiffré, en acceptant l'erreur que cela introduit.

const q = 3329;

// Compress_d : ramène un élément de Z_q sur d bits.
function compresser(x, d) {
  // À COMPLÉTER — arrondir (2^d / q) · x, puis réduire modulo 2^d.
  return 0;
}

// Decompress_d : retour approximatif vers Z_q.
function decompresser(y, d) {
  // À COMPLÉTER — arrondir (q / 2^d) · y.
  return 0;
}

// Écart centré dans Z_q : 3328 est à distance 1 de 0.
const ecart = (a, b) => {
  const d = Math.abs(a - b) % q;
  return Math.min(d, q - d);
};

console.log("d | bits/coef | erreur max | erreur moyenne | borne q/2^(d+1)");
for (const d of [12, 11, 10, 5, 4, 3]) {
  let max = 0, total = 0;
  for (let x = 0; x < q; x++) {
    const e = ecart(x, decompresser(compresser(x, d), d));
    max = Math.max(max, e);
    total += e;
  }
  console.log(
    `${String(d).padStart(2)} | ${String(d).padStart(9)} | ${String(max).padStart(10)}` +
    ` | ${(total / q).toFixed(2).padStart(14)} | ${(q / 2 ** (d + 1)).toFixed(1).padStart(15)}`
  );
}

// Taille du chiffré ML-KEM : 32 · (du·k + dv) octets.
console.log("\nchiffré ML-KEM selon (du, dv) :");
for (const [nom, k, du, dv] of [["512", 2, 10, 4], ["768", 3, 10, 4], ["1024", 4, 11, 5]]) {
  console.log(`  ML-KEM-${nom.padEnd(4)} k=${k} du=${du} dv=${dv}  →  ${32 * (du * k + dv)} octets`);
}

const q = 3329;

function compresser(x, d) {
  // L'arrondi est la seule chose qui se passe ici : on projette Z_q, qui a
  // 3329 éléments, sur 2^d valeurs. Toute l'information au-delà de d bits
  // est jetée volontairement.
  return Math.round((2 ** d / q) * x) % 2 ** d;
}

function decompresser(y, d) {
  return Math.round((q / 2 ** d) * y);
}

const ecart = (a, b) => {
  const d = Math.abs(a - b) % q;
  return Math.min(d, q - d);
};

console.log("d | bits/coef | erreur max | erreur moyenne | borne q/2^(d+1)");
for (const d of [12, 11, 10, 5, 4, 3]) {
  let max = 0, total = 0;
  for (let x = 0; x < q; x++) {
    const e = ecart(x, decompresser(compresser(x, d), d));
    max = Math.max(max, e);
    total += e;
  }
  console.log(
    `${String(d).padStart(2)} | ${String(d).padStart(9)} | ${String(max).padStart(10)}` +
    ` | ${(total / q).toFixed(2).padStart(14)} | ${(q / 2 ** (d + 1)).toFixed(1).padStart(15)}`
  );
}

console.log("\nchiffré ML-KEM selon (du, dv) :");
for (const [nom, k, du, dv] of [["512", 2, 10, 4], ["768", 3, 10, 4], ["1024", 4, 11, 5]]) {
  console.log(`  ML-KEM-${nom.padEnd(4)} k=${k} du=${du} dv=${dv}  →  ${32 * (du * k + dv)} octets`);
}

// Trois lectures de la table.
//
// 1. L'erreur maximale colle à la borne théorique q / 2^(d+1). Ce n'est pas
//    une coïncidence : arrondir sur 2^d niveaux découpe Z_q en intervalles
//    de largeur q/2^d, et l'erreur d'arrondi vaut au plus la moitié.
//
// 2. Passer de 12 à 10 bits par coefficient économise 17 % du chiffré et
//    coûte une erreur de l'ordre de 1,6 — dérisoire devant le bruit LWE
//    déjà présent. C'est un excellent marché, et c'est pourquoi du = 10.
//
// 3. dv = 4 sur le second terme paraît brutal (erreur ~104) et ne l'est
//    pas : ce terme ne porte qu'UN BIT de message par coefficient, décodé
//    en comparant à q/2 ≈ 1664. Une erreur de 104 reste très loin du seuil.
//    Chaque terme est compressé selon ce qu'il transporte, pas uniformément.
//
// C'est tout le raisonnement de dimensionnement de ML-KEM : la compression
// ajoute du bruit, le bruit ajouté doit rester sous le budget qui sépare
// encore du seuil de décodage, et ce budget résiduel fixe le taux d'échec
// de déchiffrement.

À retenir

Le NIST a normalisé deux signatures à base de réseaux plutôt qu'une, et ce n'est pas une indécision. ML-DSA (FIPS 204) est le choix par défaut, robuste et simple à implémenter. Falcon produit des signatures deux à quatre fois plus courtes, au prix d'une implémentation que peu d'équipes savent écrire correctement. Ce chapitre explique le mécanisme commun, puis ce qui les sépare.

Signer avec un réseau : le piège

L'idée naturelle a été essayée, et elle a échoué. Elle mérite d'être racontée, parce que la solution ne se comprend qu'en fonction du problème.

Dans le schéma GGH, puis dans NTRUSign, signer consistait à résoudre CVP : le message donne un point du plan, la signature est le point du réseau le plus proche, calculé grâce à la bonne base secrète. Vérifier consistait à contrôler que la signature est un point du réseau proche du message — ce qui ne demande que la base publique.

Le raisonnement est correct. Il est aussi fatal. Chaque signature est un vecteur dont l'écart au message est distribué dans la cellule fondamentale de la base secrète. Collectez quelques milliers de signatures, et la forme de cette cellule apparaît. Nguyen et Regev l'ont formalisé en 2006 sous le nom d'apprentissage du parallélépipède : quelques centaines de signatures suffisaient à reconstruire la clé privée de NTRUSign.

La leçon est générale et vaut d'être martelée en cours : une signature qui dépend statistiquement du secret finit par le révéler. Le nombre de signatures qu'un attaquant peut collecter n'est pas borné.

Fiat-Shamir avec avortements

La réponse de Lyubashevsky est le paradigme de ML-DSA. On part d'un protocole d'identification à trois passes — engagement, défi, réponse — qu'on rend non interactif en calculant le défi comme un haché du message et de l'engagement : c'est la transformation de Fiat-Shamir.

Le masque $y$, tiré uniformément et frais à chaque signature, cache le secret $s$. Mais il ne le cache pas toujours : selon les tirages, $z$ peut sortir de la plage atteignable sans $s$, et cette sortie est corrélée au secret. C'est exactement le défaut de NTRUSign, en plus discret.

D'où l'avortement. On n'accepte $z$ que s'il tombe dans une fenêtre réduite, $\|z\|_\infty \leq \gamma - \beta$, atteignable quel que soit le secret. Sinon on jette tout — y compris le défi — et on recommence avec un nouveau masque.

Ce que le rejet achète est précis : la loi de $z$ devient indépendante de $s$. Le simulateur de la preuve de sécurité peut alors produire des signatures parfaitement distribuées sans connaître le secret, ce qui est exactement ce qu'exige une réduction. La signature ne fuit plus rien, parce qu'elle ne dépend statistiquement plus de rien.

Le prix est un nombre de tours aléatoire. Retenez-le : c'est un temps d'exécution variable au cœur d'une opération secrète, et le chapitre 12 en fera son miel.

ML-DSA en pratique

ML-DSA repose simultanément sur Module-LWE — pour que la clé publique cache le secret — et sur Module-SIS — pour qu'on ne puisse pas forger une réponse courte sans le connaître. Il travaille dans le même anneau que ML-KEM, avec $n = 256$, mais un module $q = 8\,380\,417$ qui autorise la NTT complète.

Deux détails d'ingénierie méritent une mention en cours.

Le premier est le mécanisme d'indices. Transmettre $w$ en entier coûterait très cher. On ne transmet que ses bits de poids fort, plus un petit « indice » qui permet au vérificateur de reconstituer ce dont il a besoin. C'est une compression, comme dans ML-KEM, et elle explique une bonne part de l'écart entre la taille naïve et la taille réelle.

Le second est le caractère aléatoire de la signature. La FIPS 204 prévoit une variante déterministe, où le masque est dérivé du message et de la clé, et une variante « couverte » qui y ajoute de l'aléa frais — cette dernière étant le défaut. La raison est défensive : une signature déterministe se signe deux fois à l'identique, ce qui permet à un attaquant capable d'injecter une faute de comparer les deux exécutions et d'en déduire le secret. Le déterminisme, qui est une vertu pour la reproductibilité, est ici une prise.

Falcon : plus court, plus difficile

Falcon suit une voie entièrement différente, le cadre GPV : une trappe permet d'échantillonner un vecteur court du réseau, proche d'une cible donnée, selon une distribution gaussienne exactement calibrée. C'est cette calibration qui empêche la fuite — au lieu de rejeter comme ML-DSA, on échantillonne directement dans la bonne loi.

Le réseau employé est un réseau NTRU, plus compact que les réseaux modulaires, d'où des objets nettement plus petits :

Pourquoi ML-DSA reste-t-il le choix par défaut malgré cet écart ? À cause de l'implémentation, et c'est un point que les étudiants doivent entendre clairement.

L'échantillonneur gaussien de Falcon exige de l'arithmétique à virgule flottante en double précision. Un schéma cryptographique qui dépend du comportement exact du flottant est fragile : les résultats varient d'une architecture à l'autre, et les plateformes embarquées sans unité flottante sont exclues ou forcées à une émulation lente. Surtout, écrire cet échantillonneur en temps constant est notoirement délicat, et des attaques par canaux auxiliaires visant précisément l'échantillonnage gaussien ont été publiées.

ML-DSA, lui, ne manipule que des entiers, et son rejet — quoique de durée variable — se protège par des techniques bien comprises. On a préféré le schéma qu'on sait implémenter correctement, exactement comme au chapitre 3 pour le choix de la binomiale contre la gaussienne. C'est une constante de la conception post-quantique.

À vous

L'exercice reproduit la fuite en une dimension. Sans rejet, le secret se lit dans une simple moyenne — pas de cryptanalyse, pas de réseau, une moyenne.

// Pourquoi ML-DSA rejette. Version à une dimension, mais le mécanisme est
// exactement celui du schéma normalisé.
//
//   secret s, masque y uniforme dans [-γ, γ], défi c ∈ {0, 1}
//   réponse z = y + c·s
//
// Sans rejet, la loi de z DÉPEND de s. Avec rejet, elle n'en dépend plus.

const SECRET = 7;       // ce que l'attaquant cherche
const GAMMA = 100;      // amplitude du masque
const BETA = 10;        // borne sur |c·s|, connue publiquement
const N = 200000;

const alea = (a, b) => a + Math.floor(Math.random() * (b - a + 1));

// Signature SANS rejet : on renvoie z quoi qu'il arrive.
function signerNaif() {
  const y = alea(-GAMMA, GAMMA);
  const c = alea(0, 1);
  return { z: y + c * SECRET, c, accepte: true };
}

// Signature AVEC rejet : on ne renvoie z que s'il tient dans la fenêtre
// réduite [-(γ-β), γ-β], atteignable quel que soit le secret.
function signerAvecRejet() {
  const y = alea(-GAMMA, GAMMA);
  const c = alea(0, 1);
  const z = y + c * SECRET;
  // À COMPLÉTER — n'accepter que si |z| ≤ GAMMA - BETA.
  const accepte = true;
  return { z, c, accepte };
}

// L'attaque : moyenner les z des signatures où c = 1. Sans rejet, cette
// moyenne converge vers le secret.
function attaque(signer, nom) {
  let somme = 0, compte = 0, produites = 0, tours = 0;
  while (produites < N) {
    tours++;
    const sig = signer();
    if (!sig.accepte) continue;
    produites++;
    if (sig.c === 1) { somme += sig.z; compte++; }
  }
  console.log(
    `${nom.padEnd(16)} moyenne(z | c=1) = ${(somme / compte).toFixed(3).padStart(7)}` +
    `   secret réel = ${SECRET}   tours/signature = ${(tours / produites).toFixed(2)}`
  );
}

attaque(signerNaif, "sans rejet");
attaque(signerAvecRejet, "avec rejet");

const SECRET = 7;
const GAMMA = 100;
const BETA = 10;
const N = 200000;

const alea = (a, b) => a + Math.floor(Math.random() * (b - a + 1));

function signerNaif() {
  const y = alea(-GAMMA, GAMMA);
  const c = alea(0, 1);
  return { z: y + c * SECRET, c, accepte: true };
}

function signerAvecRejet() {
  const y = alea(-GAMMA, GAMMA);
  const c = alea(0, 1);
  const z = y + c * SECRET;
  // La fenêtre [-(γ-β), γ-β] est INCLUSE dans l'image de y + c·s pour tout
  // secret admissible. Restreindre z à cette fenêtre rend donc sa loi
  // uniforme sur elle — indépendamment de s, de c, et de tout le reste.
  const accepte = Math.abs(z) <= GAMMA - BETA;
  return { z, c, accepte };
}

function attaque(signer, nom) {
  let somme = 0, compte = 0, produites = 0, tours = 0;
  while (produites < N) {
    tours++;
    const sig = signer();
    if (!sig.accepte) continue;
    produites++;
    if (sig.c === 1) { somme += sig.z; compte++; }
  }
  console.log(
    `${nom.padEnd(16)} moyenne(z | c=1) = ${(somme / compte).toFixed(3).padStart(7)}` +
    `   secret réel = ${SECRET}   tours/signature = ${(tours / produites).toFixed(2)}`
  );
}

attaque(signerNaif, "sans rejet");
attaque(signerAvecRejet, "avec rejet");

// Ce que la sortie montre, et qui est le cœur du chapitre.
//
// SANS REJET : la moyenne des z pour lesquels c = 1 converge vers 7. Le
// secret se lit directement dans une statistique sur les signatures. Aucune
// cryptanalyse, aucun réseau, aucune réduction : une moyenne. C'est la
// fuite qui a tué NTRUSign, à ceci près qu'il fallait là-bas reconstruire
// un parallélépipède au lieu de calculer une moyenne.
//
// AVEC REJET : la moyenne tombe à zéro. La loi de z est uniforme sur
// [-90, 90] QUEL QUE SOIT le secret — c'est ce qui permet au simulateur de
// la preuve de sécurité de produire des signatures sans connaître s.
//
// Le prix se lit dans la dernière colonne : environ 1,1 tour par signature
// ici. Pour ML-DSA-65, avec beaucoup plus de coefficients à faire tenir
// simultanément dans la fenêtre, l'espérance monte à quelques tours — et
// surtout, elle est ALÉATOIRE. Un signataire dont le temps d'exécution
// laisse voir le nombre de tours redonne à l'attaquant une information
// corrélée au secret : c'est le chapitre 12.

À retenir

QCM du bloc I — Réseaux euclidiens

Douze questions sur les quatre chapitres du bloc — c'est le plus long du cursus, et celui dont tout le reste dépend. Si vous devez n'en réussir qu'un, c'est celui-ci.