Outils mathématiques

Trois objets reviennent dans tous les chapitres qui suivent : un anneau de polynômes, une distribution de bruit, et une notion de réduction entre problèmes. Ce chapitre les installe proprement, pour n'avoir plus à s'interrompre ensuite. Il est court et instrumental : rien ici n'est de la cryptographie, tout y sert.

L'anneau de travail : $\mathbb{Z}_q[X]/(X^n+1)$

ML-KEM et ML-DSA ne manipulent pas des vecteurs d'entiers mais des polynômes. L'anneau est toujours le même :

Un élément est un polynôme de degré au plus $n-1$ dont les coefficients sont pris modulo $q$. Il y a donc deux réductions simultanées, et les confondre est l'erreur classique. Le modulo $q$ borne les coefficients ; le modulo $X^n+1$ borne le degré. La seconde est la plus intéressante : puisque $X^n \equiv -1$, tout terme de degré $n+k$ revient en degré $k$ avec un signe moins. On appelle cela la convolution négacyclique.

Regardez la dernière étape de l'animation : c'est là que tout se joue. Les huit premiers produits sont ceux d'une multiplication de polynômes ordinaire. Le neuvième déborde, et le terme de degré 4 ne disparaît pas — il revient en degré 0 en changeant de signe.

Pourquoi $X^n+1$ et pas $X^n-1$

La question paraît cosmétique. Elle ne l'est pas.

Dans l'anneau cyclique $\mathbb{Z}_q[X]/(X^n-1)$, le polynôme $X^n-1$ se factorise toujours : il admet $X = 1$ pour racine. Évaluer un polynôme en $1$ revient à sommer ses coefficients, et cette évaluation est un homomorphisme d'anneaux. Il existe donc une projection non triviale de l'anneau vers $\mathbb{Z}_q$ — un canal par lequel de l'information sur les facteurs s'échappe, et qui permet à un attaquant de travailler en dimension 1 au lieu de $n$.

Dans l'anneau négacyclique, avec $n$ puissance de 2, le polynôme $X^n+1$ est le $2n$-ième polynôme cyclotomique. Il est irréductible sur $\mathbb{Q}$, l'anneau correspondant est l'anneau des entiers d'un corps de nombres, et la projection n'existe pas. Un signe sépare un anneau exploitable d'un anneau qui ne l'est pas. L'exercice de fin de chapitre vous fait mesurer la différence à la main.

La NTT, et pourquoi $q$ est ce qu'il est

Multiplier deux polynômes de degré 255 coûte $256^2 = 65\,536$ multiplications par la méthode naïve. C'est l'opération la plus fréquente de ML-KEM : elle doit être rapide.

La solution est la transformée en théorie des nombres, la NTT — une transformée de Fourier discrète où les racines de l'unité complexes sont remplacées par des racines de l'unité dans $\mathbb{Z}_q$. Elle ramène le coût à $O(n \log n)$, parce que dans le domaine transformé la multiplication devient point à point.

Encore faut-il que ces racines existent, et c'est ce qui dicte le choix de $q$. Une racine primitive $2n$-ième de l'unité existe dans $\mathbb{Z}_q$ si et seulement si $q \equiv 1 \pmod{2n}$.

Le détail mérite un instant. Pour ML-KEM, $q - 1 = 3328$ est divisible par 256 mais pas par 512 : il existe une racine 256-ième de l'unité, pas de racine 512-ième. La NTT ne peut donc pas descendre jusqu'à des polynômes constants ; elle s'arrête à 128 polynômes de degré 1, et la multiplication point à point est en réalité une multiplication de petits polynômes. Ce n'est pas une négligence : $q = 3329$ a été choisi le plus petit possible pour réduire la taille des clés, et cette NTT incomplète est le prix payé. ML-DSA, moins contraint sur la taille, prend un $q$ qui autorise la NTT complète.

Le bruit : gaussienne ou binomiale centrée

Tous les schémas à réseaux ajoutent du bruit. Sa distribution n'est pas un détail d'implémentation — la preuve de sécurité en dépend, et les attaques par canaux auxiliaires la visent en priorité.

La gaussienne discrète sur $\mathbb{Z}$, de paramètre $\sigma$, attribue à chaque entier $x$ une probabilité proportionnelle à $\exp(-x^2 / 2\sigma^2)$. C'est la distribution des preuves : les réductions de Regev et d'Ajtai sont énoncées pour elle. C'est aussi un cauchemar d'implémentation, parce qu'échantillonner une gaussienne en temps constant demande des tables ou des rejets soigneusement écrits. Falcon paie ce prix, et le chapitre 7 expliquera pourquoi il n'a pas le choix.

La binomiale centrée $\mathrm{CBD}(\eta)$ est la réponse pragmatique. On tire $2\eta$ bits aléatoires et on renvoie la somme des $\eta$ premiers moins la somme des $\eta$ derniers. Le résultat est dans $[-\eta, \eta]$, la distribution est symétrique et grossièrement en cloche, et l'échantillonnage est naturellement en temps constant : compter des bits ne branche pas. ML-KEM et ML-DSA l'utilisent, avec $\eta$ valant 2 ou 3. La preuve de sécurité est alors adaptée à cette distribution plutôt qu'à la gaussienne.

C'est un arbitrage exemplaire, et il vaut d'être souligné en cours : on a préféré une distribution moins élégante mais implémentable sûrement. Le chapitre 12 montrera ce que coûte le choix inverse.

Réductions : ce que « se réduit à » veut dire

Dernier outil, et le plus important conceptuellement. Dire qu'un schéma « repose sur LWE » signifie qu'on a construit une réduction : un algorithme qui, disposant d'un attaquant contre le schéma, résout LWE. La contraposée est l'énoncé utile — si LWE est difficile, alors le schéma est sûr.

Deux qualités distinguent les bonnes réductions des autres.

Une réduction est serrée si l'attaquant construit contre le problème difficile a une efficacité comparable à celle de l'attaquant contre le schéma. Une réduction lâche, qui perd un facteur $2^{40}$, oblige à surdimensionner les paramètres pour compenser — ou bien on l'ignore, ce qui se fait plus souvent qu'on ne l'admet.

Une réduction est du pire cas vers le cas moyen si elle transforme un attaquant qui réussit sur des instances aléatoires en un algorithme qui résout toutes les instances. C'est la propriété remarquable des réseaux, absente de RSA : personne ne sait montrer que factoriser un module RSA tiré au hasard est aussi difficile que factoriser le pire module possible. Le chapitre 5 énoncera précisément la réduction de Regev, qui donne cette garantie à LWE.

À vous

Deux fonctions de dix lignes, et le troisième test répond à la question du chapitre : pourquoi un signe change tout.

// L'anneau de travail de ML-KEM et ML-DSA : Z_q[X]/(X^n + 1).
// Ici en miniature — q = 17, n = 4 — pour que tout soit vérifiable à la main.

const q = 17;
const n = 4;

const mod = (x) => ((x % q) + q) % q;

// Multiplication NÉGACYCLIQUE : les degrés ≥ n reviennent en degré (deg - n)
// AVEC UN SIGNE MOINS, parce que X^n ≡ −1 dans cet anneau.
function multiplier(f, g) {
  const r = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      const deg = i + j;
      // À COMPLÉTER — deux cas : deg < n, et deg ≥ n (repli avec signe).
      r[deg % n] = mod(r[deg % n] + f[i] * g[j]);
    }
  }
  return r;
}

// Variante CYCLIQUE, pour comparer : X^n ≡ +1. C'est l'anneau qu'on
// N'UTILISE PAS, et la suite montre pourquoi.
function multiplierCyclique(f, g) {
  const r = new Array(n).fill(0);
  for (let i = 0; i < n; i++)
    for (let j = 0; j < n; j++) r[(i + j) % n] = mod(r[(i + j) % n] + f[i] * g[j]);
  return r;
}

const afficher = (p) =>
  "[" + p.map((c) => String(c).padStart(2)) + "]";

const f = [1, 2, 3, 4];
const g = [5, 6, 0, 0];

console.log("f            =", afficher(f));
console.log("g            =", afficher(g));
console.log("f × g        =", afficher(multiplier(f, g)), "  attendu [15, 16, 10,  4]");
console.log("f ×cyc g     =", afficher(multiplierCyclique(f, g)));

// Test 1 — X^n doit valoir −1, c'est la définition de l'anneau.
const X = [0, 1, 0, 0];
let Xn = [1, 0, 0, 0];
for (let k = 0; k < n; k++) Xn = multiplier(Xn, X);
console.log("\nX^4          =", afficher(Xn), "  attendu [16,  0,  0,  0]  (soit −1)");

// Test 2 — la somme des coefficients est-elle un invariant ?
const somme = (p) => mod(p.reduce((a, b) => a + b, 0));
console.log("\nsomme(f)×somme(g) =", mod(somme(f) * somme(g)));
console.log("somme(f ×cyc g)   =", somme(multiplierCyclique(f, g)), " ← égal : un homomorphisme");
console.log("somme(f × g)      =", somme(multiplier(f, g)), " ← différent : pas d'homomorphisme");

À retenir

QCM du bloc 0 — Socle et menace quantique

Neuf questions sur les trois premiers chapitres. Elles ne reprennent aucun quiz de leçon : chacune demande de transposer sur une situation nouvelle, et plusieurs croisent deux chapitres. Le bilan final nomme les chapitres à reprendre.