Cryptographie post-quantique · C1 Socle et menace quantique · Chapitre 3 · 3 h

Outils mathématiques

Anneaux de polynômes Z_q[X]/(X^n+1), échantillonnage gaussien, corps finis, rappels de complexité et de réductions.

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 :

R_q = \mathbb{Z}_q[X] / (X^n + 1), \qquad n \text{ puissance de } 2

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.

Animation · 9 étapes

(1 + 2X + 3X² + 4X³) × (5 + 6X) dans Z₁₇[X]/(X⁴+1)

Quatre cases, une par degré — Un élément de l'anneau est un polynôme de degré au plus 3 : quatre coefficients, tous pris modulo 17. On accumule les produits croisés dans ces quatre cases.
f₀ · g₀ → degré 0 — Le produit des termes constants va en case 0. Rien de surprenant pour l'instant.
f₀ · g₁ → degré 1 — Les degrés s'additionnent, comme dans tout produit de polynômes.
f₁ · g₀ → degré 1 — Deuxième contribution au degré 1 : 6 + 10 = 16. On accumule dans la même case.
f₁ · g₁ → degré 2 — Rien de neuf. Le calcul reste celui d'un produit ordinaire.
f₂ · g₀ → degré 2, et le modulo entre en jeu — 12 + 15 = 27, mais on travaille modulo 17 : la case vaut 10. Le modulo q borne les coefficients ; il ne provoque aucun repli de degré.
f₂ · g₁ → degré 3 — 18 mod 17 = 1. Dernier degré représentable dans l'anneau.
f₃ · g₀ → degré 3 — 1 + 20 = 21 ≡ 4 mod 17. Il ne reste plus qu'un produit croisé.
f₃ · g₁ → degré 4 : le repli négacyclique — Le degré 4 n'existe pas dans l'anneau. Comme X⁴ ≡ −1, le terme revient en degré 0 avec un SIGNE MOINS : 5 − 24 = −19 ≡ 15 mod 17. C'est là toute la différence avec un anneau cyclique, où il reviendrait avec un plus. Le résultat est 15 + 16X + 10X² + 4X³.

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.

Quiz · 1 question

Dans Z_q[X]/(X⁴+1), que devient le terme 24·X⁴ ?

Il disparaît — annulé
Il devient 24 en degré 0 — repli cyclique
Il devient −24 en degré 0 — repli négacyclique

Réponse : X⁴ ≡ −1, donc 24·X⁴ ≡ −24. Le terme revient en degré 0 avec un changement de signe. S'il revenait avec un plus, on serait dans l'anneau cyclique Z_q[X]/(X⁴−1) — celui qui possède l'homomorphisme d'évaluation en 1, et qu'on évite précisément pour cette raison.

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}$ .

Schéma	$q$	$n$	$q - 1$	NTT
ML-KEM	3329	256	$2^8 \times 13$	incomplète
ML-DSA	8380417	256	$2^{13} \times 3 \times 11 \times 31$	complète

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.

Quiz · 1 question

Pourquoi ML-KEM préfère-t-il une binomiale centrée à une gaussienne discrète ?

Parce que la binomiale donne une meilleure sécurité prouvée
Parce qu'elle s'échantillonne naturellement en temps constant, en comptant des bits
Parce que la gaussienne discrète n'est pas définie sur les entiers

Réponse : La gaussienne est la distribution des preuves originelles — elle n'est pas moins sûre, au contraire. Mais l'échantillonner en temps constant demande des tables ou des boucles de rejet délicates, et c'est une source d'attaques par canaux auxiliaires bien documentée. Compter des bits, en revanche, ne branche jamais. La preuve a été refaite pour la binomiale : on a adapté la théorie à ce qu'on savait implémenter sûrement.

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.

Exercice de code

Implémentez le repli négacyclique, puis comparez avec la variante cyclique : le troisième test explique à lui seul le choix de X^n + 1.

Point de départ

// 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");

Solution

const q = 17;
const n = 4;

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

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;
      // Le repli négacyclique tient en un signe. C'est la seule différence
      // avec un produit de polynômes ordinaire — et elle suffit à changer
      // la structure algébrique de l'anneau.
      const signe = deg >= n ? -1 : 1;
      const cible = deg % n;
      r[cible] = mod(r[cible] + signe * f[i] * g[j]);
    }
  }
  return r;
}

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)));

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)");

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");

// Le troisième test est le plus instructif, et c'est celui qu'on saute
// d'habitude.
//
// Dans l'anneau CYCLIQUE Z_q[X]/(X^n − 1), évaluer un polynôme en X = 1
// revient à sommer ses coefficients, et cette évaluation est un
// HOMOMORPHISME d'anneaux : somme(f × g) = somme(f) × somme(g). Autrement
// dit, l'anneau possède une projection non triviale vers Z_q — un canal par
// lequel de l'information sur les facteurs s'échappe, et sur lequel un
// attaquant peut monter une attaque en dimension 1 au lieu de n.
//
// Dans l'anneau NÉGACYCLIQUE, X^n + 1 est le 2n-ième polynôme cyclotomique
// quand n est une puissance de 2 : il est IRRÉDUCTIBLE sur Q, l'anneau est
// un corps de nombres, et cette projection n'existe pas.
//
// C'est pour cela que ML-KEM et ML-DSA travaillent modulo X^256 + 1 et non
// modulo X^256 − 1. Un signe.

À retenir

Flashcards · 3 cartes

Quelles sont les DEUX réductions simultanées dans Z_q[X]/(Xⁿ+1) ?: Le modulo q borne les COEFFICIENTS ; le modulo Xⁿ+1 borne le DEGRÉ. La seconde est négacyclique : un terme de degré n+k revient en degré k avec un signe moins, puisque Xⁿ ≡ −1.
Pourquoi Xⁿ+1 plutôt que Xⁿ−1 ?: Xⁿ−1 admet 1 pour racine, donc l'évaluation en 1 — la somme des coefficients — est un homomorphisme vers Z_q : une projection non triviale par laquelle de l'information s'échappe. Pour n puissance de 2, Xⁿ+1 est le 2n-ième polynôme cyclotomique, irréductible sur Q, et cette projection n'existe pas.
Qu'est-ce qu'une réduction du pire cas vers le cas moyen, et pourquoi est-ce rare ?: Elle transforme un attaquant qui réussit sur des instances aléatoires en un algorithme résolvant TOUTES les instances : casser le schéma en moyenne implique casser le problème au pire. Les réseaux l'offrent (Ajtai, Regev) ; RSA non — nul ne sait relier la difficulté d'un module tiré au hasard à celle du pire module.

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.

QCM de bloc · 9 questions

Socle et menace quantique

1. Une entreprise chiffre ses sauvegardes en AES-256 et protège la clé de chiffrement par RSA-2048. Où se situe le risque quantique ?

Dans AES-256, que Grover ramène à 128 bits
Dans RSA-2048, qui protège la clé : l'ensemble ne vaut que son maillon asymétrique
Nulle part : des sauvegardes hors ligne ne sont pas interceptables

Réponse : AES-256 tient parfaitement, et l'hypothèse « hors ligne » ne dit rien de la façon dont la clé a circulé. Le maillon faible est RSA-2048 : quiconque a intercepté l'échange de la clé pourra la déchiffrer plus tard et lire des sauvegardes pourtant chiffrées en AES-256. Un chaînage ne vaut jamais mieux que son composant le plus faible.

2. Système A : X = 1 an, Y = 8 ans. Système B : X = 40 ans, Y = 1 an. Lequel traiter en premier ?

B — X domine largement l'inégalité, et sa marge est très négative dans tous les scénarios
A — sa migration est la plus longue, il faut donc s'y prendre au plus tôt
Les deux : X + Y est du même ordre de grandeur dans les deux cas

Réponse : X + Y vaut 9 pour A et 41 pour B : ce n'est pas du même ordre. Un Y long est un argument pour commencer tôt, mais il ne crée pas d'urgence si la donnée perd toute valeur en un an. C'est X qui décide, et c'est ce qui rend le classement de Mosca contre-intuitif.

3. Pourquoi le logarithme discret tombe-t-il en même temps que la factorisation ?

Parce que Shor a publié deux algorithmes distincts la même année
Parce qu'ECDSA emploie RSA en interne pour la génération de ses clés
Parce que les deux se ramènent à la recherche d'une période dans un groupe abélien fini

Réponse : Un seul algorithme les emporte tous les deux, et c'est ce qui rend la nouvelle si mauvaise. La factorisation comme le logarithme discret se reformulent en recherche de période, et c'est cette période que la transformée de Fourier quantique extrait. La diversification à laquelle on croyait — « nous avons RSA et les courbes » — n'existait pas.

4. Un fournisseur annonce une machine à 1000 qubits. Quelle question posez-vous avant de conclure quoi que ce soit ?

Combien de qubits LOGIQUES cela donne une fois la correction d'erreur appliquée
Quelle est la fréquence d'horloge du processeur quantique
Aucune : 1000 qubits suffisent à factoriser RSA-2048

Réponse : Les annonces se comptent en qubits physiques, bruités ; les estimations d'attaque se comptent en qubits logiques, corrigés. Le rapport se compte aujourd'hui en centaines ou milliers de qubits physiques par qubit logique. Confondre les deux fait varier le pronostic de plusieurs ordres de grandeur — et 1000 qubits physiques sont très loin du compte.

5. Grover appliqué à la recherche de COLLISIONS sur SHA-256 :

ramène la résistance de 128 à 64 bits
n'apporte qu'un gain marginal : le paradoxe des anniversaires domine déjà le calcul
ramène la résistance à zéro, comme Shor sur RSA

Réponse : Attention à ne pas confondre les deux résistances. En PRÉIMAGE, SHA-256 offre 256 bits et Grover les ramène à 128. En COLLISION, l'attaque des anniversaires donne déjà 128 bits classiquement, et les variantes quantiques n'améliorent cela que marginalement, au prix d'une mémoire considérable. La colonne « collision » du tableau du chapitre 1 est donc la seule qui ne bouge presque pas.

6. Pourquoi ML-KEM ne peut-il pas employer une NTT complète, alors que ML-DSA le peut ?

Parce que n = 256 est trop petit pour une NTT complète
Parce que ML-KEM n'emploie pas de NTT du tout
Parce que q − 1 = 3328 est divisible par 256 mais pas par 512 : il n'existe pas de racine 512-ième de l'unité

Réponse : Les deux schémas partagent n = 256 et emploient tous deux une NTT. C'est le module qui diffère : 3328 = 2⁸ × 13 s'arrête à 256, alors que 8 380 416 = 2¹³ × 3 × 11 × 31 va bien au-delà de 512. La NTT de ML-KEM s'arrête donc à 128 polynômes de degré 1 — prix assumé d'un q petit, choisi pour réduire la taille des clés.

7. Une équipe propose de remplacer la binomiale centrée de ML-KEM par une gaussienne discrète, « plus conforme aux preuves d'origine ». Que répondez-vous ?

Bonne idée : la preuve de sécurité en serait plus directe
La preuve a été refaite pour la binomiale, et l'échantillonnage gaussien en temps constant est une source documentée de fuites
Impossible : une gaussienne n'est pas définie sur les entiers

Réponse : La gaussienne discrète existe bien sur les entiers, et c'est effectivement la distribution des preuves de Regev. Mais l'argument de conformité est vide : la preuve a été refaite pour la binomiale. Et l'argument d'implémentation est décisif — compter des bits ne branche jamais, échantillonner une gaussienne en temps constant est délicat et a déjà donné lieu à des attaques. On adapte la théorie à ce qu'on sait implémenter sûrement.

8. Qu'interdit exactement une réduction du pire cas vers le cas moyen ?

L'existence de clés accidentellement faibles parmi celles qu'on tire au hasard
L'existence de tout algorithme d'attaque sous-exponentiel
Que le problème appartienne à NP ∩ coNP

Réponse : Elle relie la difficulté moyenne à la difficulté du pire cas : casser des instances tirées au hasard reviendrait à résoudre TOUTES les instances. Le tirage ne peut donc pas tomber sur une instance accidentellement facile. Elle ne dit rien du coût des meilleures attaques connues, ni de la classe de complexité — le problème approché est justement dans NP ∩ coNP pour γ ≥ √n.

9. Un routeur industriel déployé pour vingt ans vérifie des signatures ECDSA sur ses mises à jour de firmware. Quelle priorité de migration ?

Faible : la récolte anticipée ne concerne pas les signatures
Nulle : un firmware n'est pas une donnée confidentielle
Élevée : la durée de VÉRIFICATION joue le rôle de X, et le matériel n'est pas agile

Réponse : Les deux premières affirmations sont exactes et ne concluent rien. La récolte anticipée ne menace pas les signatures, mais le routeur devra vérifier des signatures pendant vingt ans : le jour où l'on sait forger de l'ECDSA, on pousse ce qu'on veut sur le parc. Et remplacer une racine de confiance gravée dans du silicium n'est pas une mise à jour logicielle — Y est irréductible.

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

Pourquoi Xn+1X^n+1Xn+1 et pas Xn−1X^n-1Xn−1

La NTT, et pourquoi qqq est ce qu'il est