Un cours de cryptographie post-quantique commence toujours par le même risque : verser dans l'annonce d'apocalypse ou dans le haussement d'épaules. Les deux sont des erreurs d'ingénieur. Ce chapitre pose la question dans les termes où elle se décide réellement — quelles données, pendant combien de temps, et à partir de quand.

Ce sur quoi repose la cryptographie déployée

Presque tout ce qui protège une communication aujourd'hui tient sur deux hypothèses de difficulté, et deux seulement.

La factorisation : étant donné $N = pq$ avec $p$ et $q$ premiers de 1024 bits, retrouver $p$. C'est RSA, pour le chiffrement comme pour la signature.

Le logarithme discret : étant donné $g$ et $g^x$ dans un groupe bien choisi, retrouver $x$. C'est Diffie-Hellman, DSA, et toute la famille des courbes elliptiques — ECDH, ECDSA, Ed25519 — qui ne fait que changer le groupe.

Ces deux problèmes ne sont pas indépendants au point qu'on l'espérerait. Ils partagent une structure de groupe abélien fini, et c'est exactement cette structure que l'algorithme de Shor exploite. Un seul algorithme les casse tous les deux, ce qui est une nouvelle bien pire que si chacun avait sa faiblesse propre. La diversification à laquelle on croyait — « nous avons RSA et les courbes elliptiques » — n'existait pas.

Ce qui tombe, ce qui tient

Le tableau suivant est celui à retenir du chapitre. La colonne de droite n'est pas une opinion : elle découle directement des deux algorithmes quantiques connus.

La conséquence pratique est franche. Le symétrique se répare en doublant la clé : passer de AES-128 à AES-256 restitue 128 bits de sécurité, et cela coûte quelques pourcents de performance. L'asymétrique ne se répare pas : aucune taille de clé RSA ne résiste à Shor, puisque le coût de l'attaque devient polynomial en la taille de la clé. Il faut changer de problème difficile, pas de paramètre.

Récolter maintenant, déchiffrer plus tard

Voici l'argument qui rend la question urgente alors même que la machine n'existe pas.

Un adversaire disposant de capacités d'interception peut enregistrer aujourd'hui un trafic chiffré qu'il ne sait pas lire, le stocker, et le déchiffrer le jour où il disposera d'un ordinateur quantique. Le stockage coûte peu ; la patience ne coûte rien. Ce modèle porte le nom de harvest now, decrypt later.

Il ne s'applique qu'à la confidentialité, et c'est une distinction que beaucoup de présentations escamotent. Une signature vérifiée aujourd'hui par une machine classique n'a rien à craindre d'une machine future : au moment où l'attaquant saura forger la signature, le document aura déjà été accepté ou refusé. En revanche, une signature qui devra encore être vérifiée dans quinze ans — celle d'un firmware, d'un certificat racine, d'un acte notarié — vit exactement le même problème que la confidentialité.

Retenez donc deux urgences distinctes : le chiffrement est urgent à cause de la récolte anticipée ; la signature est urgente pour ce qui a une longue durée de vérification.

L'inégalité de Mosca

Michele Mosca a proposé une formulation qui tient en une ligne et qui transforme un débat d'opinion en calcul.

$X$ est la durée pendant laquelle une donnée doit rester confidentielle. $Y$ est le temps nécessaire pour migrer le système qui la protège. $Z$ est le temps restant avant qu'existe un ordinateur quantique cryptographiquement pertinent — un CRQC, dans le vocabulaire du domaine.

L'intérêt de la formule n'est pas de prédire $Z$, qui reste inconnu. Il est de montrer que pour de grandes valeurs de $X$, la valeur de $Z$ ne change rien au verdict. Un dossier médical à protéger cinquante ans est déjà en retard dans tous les scénarios, y compris les plus optimistes. Une session TLS bancaire, dont la valeur s'évapore en quelques heures, ne l'est dans aucun.

C'est aussi la seule des trois variables sur laquelle vous avez prise : $Y$, le temps de migration, dépend de votre inventaire et de votre agilité cryptographique — le sujet du chapitre 14.

Les calendriers officiels

Trois textes structurent la migration au moment où ce cours est écrit. Vérifiez-en les versions courantes : ce sont les seules données du chapitre qui bougent chaque année.

Le NIST, dans le rapport IR 8547, propose de déclarer obsolètes après 2030 les mécanismes à 112 bits de sécurité classique — RSA, ECDSA, ECDH, Diffie-Hellman — et de les interdire après 2035. C'est un calendrier de retrait, pas de simple recommandation.

L'ANSSI a une position plus prudente sur un point précis : elle exige l'hybridation, c'est-à-dire la combinaison d'un mécanisme classique et d'un mécanisme post-quantique, et n'accepte pas un schéma post-quantique employé seul avant 2030 au plus tôt. La raison est explicite : les schémas post-quantiques sont jeunes, et l'hybridation garantit qu'une cryptanalyse surprise ne fait pas pire que l'état antérieur. Le chapitre 10, avec la cassure de SIKE, montrera que cette prudence n'est pas théorique.

La NSA, avec la suite CNSA 2.0, publie un calendrier par catégorie d'équipement pour les systèmes de sécurité nationale, avec des dates d'exclusivité échelonnées entre 2030 et 2033 selon le type de produit.

À vous

Le calcul de Mosca vaut d'être fait sur des cas concrets, parce qu'il classe les systèmes dans un ordre qui n'est pas celui de l'intuition.

// L'inégalité de Mosca : si X + Y > Z, vous êtes DÉJÀ en retard.
//
//   X = durée pendant laquelle la donnée doit rester confidentielle
//   Y = temps nécessaire pour migrer le système
//   Z = temps restant avant qu'un ordinateur quantique cryptographiquement
//       pertinent existe
//
// Les trois sont des estimations. La seule que vous maîtrisez est Y.

const ANNEE_COURANTE = 2026;

// Z est le paramètre le plus discuté. On raisonne donc par scénarios plutôt
// que par une valeur unique : c'est la bonne façon de traiter une inconnue.
const SCENARIOS = { optimiste: 25, median: 15, pessimiste: 8 };

const SYSTEMES = [
  { nom: "Dossier médical",        X: 50, Y: 4 },
  { nom: "Secret industriel",      X: 20, Y: 3 },
  { nom: "Session TLS bancaire",   X: 1,  Y: 2 },
  { nom: "Signature de firmware",  X: 15, Y: 6 },
  { nom: "Archive diplomatique",   X: 50, Y: 7 },
];

function verdict(X, Y, Z) {
  // À COMPLÉTER — renvoyez "EN RETARD" si X + Y > Z, "à surveiller" si on
  // est à moins de 3 ans de la bascule, "confortable" sinon.
  return "?";
}

for (const [nom, Z] of Object.entries(SCENARIOS)) {
  console.log(`\n── Scénario ${nom} : Z = ${Z} ans (CRQC vers ${ANNEE_COURANTE + Z}) ──`);
  for (const s of SYSTEMES) {
    console.log(
      `  ${s.nom.padEnd(24)} X+Y = ${String(s.X + s.Y).padStart(2)} ans   ${verdict(s.X, s.Y, Z)}`
    );
  }
}

const ANNEE_COURANTE = 2026;
const SCENARIOS = { optimiste: 25, median: 15, pessimiste: 8 };

const SYSTEMES = [
  { nom: "Dossier médical",        X: 50, Y: 4 },
  { nom: "Secret industriel",      X: 20, Y: 3 },
  { nom: "Session TLS bancaire",   X: 1,  Y: 2 },
  { nom: "Signature de firmware",  X: 15, Y: 6 },
  { nom: "Archive diplomatique",   X: 50, Y: 7 },
];

function verdict(X, Y, Z) {
  const marge = Z - (X + Y);
  if (marge < 0) return "EN RETARD (marge " + marge + " ans)";
  if (marge < 3) return "à surveiller (marge " + marge + " ans)";
  return "confortable (marge " + marge + " ans)";
}

for (const [nom, Z] of Object.entries(SCENARIOS)) {
  console.log(`\n── Scénario ${nom} : Z = ${Z} ans (CRQC vers ${ANNEE_COURANTE + Z}) ──`);
  for (const s of SYSTEMES) {
    console.log(
      `  ${s.nom.padEnd(24)} X+Y = ${String(s.X + s.Y).padStart(2)} ans   ${verdict(s.X, s.Y, Z)}`
    );
  }
}

// Ce que la sortie apprend, et qui n'est pas intuitif.
//
// 1. La session TLS bancaire n'est JAMAIS en retard : X = 1 an. La donnée
//    n'a aucune valeur une fois la transaction passée. Migrer d'abord les
//    systèmes les plus visibles est un réflexe, pas une priorité.
// 2. Le dossier médical est en retard dans les TROIS scénarios, y compris
//    l'optimiste. Quand X vaut 50 ans, la valeur de Z ne change plus rien :
//    le verdict est déjà tombé.
// 3. La signature de firmware est le cas subtil. Une signature ne protège
//    aucun secret — la récolte anticipée ne la menace pas. Ce qui compte
//    est la date à laquelle le matériel sera encore en service et devra
//    vérifier des signatures : c'est un X déguisé.
//
// Conclusion opérationnelle : le tri se fait sur X, pas sur la criticité
// ressentie du système.

Ce que ce chapitre ne dit pas

Trois honnêtetés pour finir, qui vous éviteront de surjouer devant un auditoire technique.

Personne ne connaît $Z$. Les estimations d'experts s'étalent sur plusieurs décennies, et elles sont produites par des gens qui ont un intérêt dans la réponse — constructeurs de machines quantiques comme vendeurs de solutions post-quantiques. Le chapitre 2 donne l'état du matériel pour que vous jugiez par vous-même.

Migrer n'est pas gratuit. Les clés et les signatures grossissent, parfois d'un facteur dix, parfois d'un facteur mille. Les handshakes se fragmentent. Certains protocoles ne supportent pas la taille des nouveaux objets. Le bloc IV traite cette facture.

Les nouveaux schémas sont jeunes. ML-KEM repose sur une hypothèse étudiée depuis une vingtaine d'années, contre quarante-cinq ans pour RSA. C'est l'argument central en faveur de l'hybridation, et c'est aussi pourquoi ce cours consacre un chapitre entier aux candidats brisés.

À retenir

Ce chapitre a un objectif précis et une limite tout aussi précise. L'objectif : comprendre pourquoi Shor casse RSA et pourquoi Grover ne casse pas AES. La limite : nous ne ferons pas un cours de mécanique quantique. Un cryptographe a besoin de savoir ce que ces algorithmes prennent en entrée, ce qu'ils rendent, et à quel coût — pas de savoir résoudre l'équation de Schrödinger.

Le qubit, sans mysticisme

Un bit classique vaut 0 ou 1. Un qubit est décrit par deux nombres complexes $\alpha$ et $\beta$ tels que $|\alpha|^2 + |\beta|^2 = 1$ :

À la mesure, on obtient 0 avec probabilité $|\alpha|^2$ et 1 avec probabilité $|\beta|^2$, et l'état est détruit. Un registre de $n$ qubits est décrit par $2^n$ amplitudes.

C'est ici que naît le malentendu le plus répandu du domaine. On lit partout qu'un ordinateur quantique « essaie toutes les possibilités en parallèle ». C'est faux, et il faut le dire fermement à des étudiants qui l'ont lu ailleurs. Les $2^n$ amplitudes existent bien, mais la mesure n'en rend qu'une seule, tirée au hasard. Un parallélisme dont on ne peut extraire qu'un résultat aléatoire ne vaut rien.

Ce qui fait la puissance de l'algorithmique quantique n'est pas la superposition, c'est l'interférence. Les amplitudes sont des nombres complexes : elles peuvent s'annuler. Un algorithme quantique utile est un algorithme qui organise les annulations de sorte que les mauvaises réponses s'éteignent mutuellement et que les bonnes se renforcent, avant la mesure. Tout le métier est là.

L'intrication est le troisième ingrédient : l'état de deux qubits n'est pas toujours décomposable en deux états individuels. C'est ce qui rend le registre irréductible à $n$ qubits séparés, et donc l'espace des états exponentiel.

La transformée de Fourier quantique

L'outil central de Shor est la transformée de Fourier quantique, la QFT. C'est la transformée de Fourier discrète habituelle, appliquée au vecteur des amplitudes.

Sa propriété décisive : elle transforme une amplitude périodique de période $r$ en une amplitude concentrée sur les multiples de $N/r$. Autrement dit, elle convertit une période — information globale, invisible sur un échantillon — en une position, qu'une mesure révèle en une fois.

Le coût est ce qui surprend. La transformée de Fourier discrète classique sur $2^n$ points coûte $O(n \, 2^n)$ opérations, ou $O(n 2^n)$ ramené à $O(2^n \log 2^n)$ par la FFT. La QFT sur $n$ qubits coûte $O(n^2)$ portes. On passe d'exponentiel à quadratique — en le nombre de qubits, ce qui n'est pas un miracle mais un changement d'unité de compte : la QFT ne donne pas accès aux $2^n$ amplitudes, elle les transforme en bloc sans jamais permettre de les lire.

Shor : une seule ligne est quantique

La factorisation se ramène à un problème de période. Pour factoriser $N$, on choisit $a$ au hasard et on cherche l'ordre $r$ de $a$ modulo $N$, c'est-à-dire le plus petit $r$ tel que $a^r \equiv 1 \pmod N$. Si $r$ est pair et $a^{r/2} \not\equiv -1$, alors

sont des facteurs non triviaux de $N$. Cette réduction est entièrement classique et date d'avant Shor. Ce que Shor a apporté, c'est une méthode quantique pour trouver $r$.

Déroulez la trace et comptez : une ligne sur neuf est quantique. C'est la formulation correcte de la menace, et elle est plus utile que l'image de la machine qui essaie tous les facteurs. Le logarithme discret tombe de la même manière, parce que trouver $x$ tel que $g^x = h$ est également un problème de période déguisé — d'où le fait qu'un seul algorithme emporte RSA, Diffie-Hellman et les courbes elliptiques.

Le coût annoncé est polynomial : de l'ordre de $O(n^3)$ opérations quantiques pour un module de $n$ bits, contre un coût sous-exponentiel pour le meilleur algorithme classique connu, le crible algébrique.

Grover : pourquoi seulement la racine carrée

Grover résout un problème différent : chercher l'unique bonne entrée parmi $N$ possibilités, quand la seule chose qu'on sache faire est tester une entrée. Il y parvient en $O(\sqrt{N})$ évaluations au lieu de $N$.

Appliqué à une clé de 128 bits, cela donne $2^{64}$ évaluations au lieu de $2^{128}$ : la sécurité est divisée par deux en bits, pas effondrée. D'où la règle simple du chapitre précédent — doubler la taille des clés symétriques.

Trois précisions rendent Grover encore moins menaçant qu'il n'en a l'air, et méritent d'être connues.

D'abord, cette borne est optimale : on sait démontrer qu'aucun algorithme quantique ne fait mieux que $\sqrt{N}$ pour une recherche non structurée. Il n'y a pas de « Grover amélioré » à craindre.

Ensuite, Grover se parallélise mal. Répartir la recherche sur $k$ machines ne divise le temps que par $\sqrt{k}$, alors qu'une recherche exhaustive classique se divise par $k$. Les $2^{64}$ évaluations doivent donc être largement séquentielles, ce qui impose une durée de calcul et une profondeur de circuit considérables.

Enfin, chaque évaluation exige d'implémenter AES en circuit quantique réversible, ce qui coûte bien plus cher qu'un tour d'AES sur un processeur ordinaire. Le NIST en tient compte dans ses niveaux de sécurité, en plafonnant la profondeur de circuit admissible.

Où en est le matériel

C'est la question que tout auditoire pose, et la seule à laquelle il faut répondre avec des ordres de grandeur plutôt qu'avec une date.

La distinction décisive est celle entre qubit physique et qubit logique. Les qubits physiques sont bruités : leur état se dégrade en quelques dizaines de microsecondes. Un qubit logique est un qubit corrigé, construit à partir de nombreux qubits physiques par un code correcteur quantique. Le rapport dépend du taux d'erreur physique et se compte aujourd'hui en centaines à milliers de qubits physiques par qubit logique.

Les machines annoncées se comptent en centaines à un millier de qubits physiques, et le franchissement du seuil de correction d'erreur — le point où ajouter des qubits physiques réduit effectivement le taux d'erreur logique — a été démontré expérimentalement, ce qui constitue le jalon scientifique important de ces dernières années.

Les estimations de ressources pour casser RSA-2048 se comptaient, dans les travaux de référence de 2019, en une vingtaine de millions de qubits physiques bruités pour quelques heures de calcul. Des travaux ultérieurs ont fait descendre cette estimation d'un ordre de grandeur. La leçon à en tirer n'est pas un chiffre — il changera encore — mais une tendance : les estimations de ressources baissent régulièrement, sous l'effet de meilleurs algorithmes autant que de meilleur matériel. Un plan de migration qui suppose que $Z$ est figé est un plan fragile.

À vous

L'exercice remplace la sous-routine quantique par une recherche naïve. Tout le reste du code est le vrai Shor. Comptez le coût de chaque partie, et vous verrez précisément ce que l'ordinateur quantique achète — et ce qu'il n'achète pas.

// Shor, mais entièrement classique : on REMPLACE la sous-routine quantique
// par une recherche naïve de période. Le reste du code est le vrai Shor.
//
// L'exercice n'a donc rien de quantique. Son but est de vous faire toucher
// du doigt QUELLE ligne est chère, et pourquoi c'est la seule qu'un
// ordinateur quantique change.

const pgcd = (a, b) => (b === 0 ? a : pgcd(b, a % b));

// Exponentiation modulaire rapide — nécessaire dès que N dépasse quelques
// milliers, sinon a^x déborde.
function puissanceMod(a, x, n) {
  let r = 1n, base = BigInt(a) % BigInt(n), e = BigInt(x), m = BigInt(n);
  while (e > 0n) {
    if (e & 1n) r = (r * base) % m;
    base = (base * base) % m;
    e >>= 1n;
  }
  return Number(r);
}

let coutPeriode = 0;

// LA sous-routine que Shor confie au quantique. Ici, force brute.
function periode(a, N) {
  // À COMPLÉTER — cherchez le plus petit r ≥ 1 tel que a^r ≡ 1 (mod N),
  // en incrémentant coutPeriode à chaque essai. Renvoyez null si r dépasse N.
  return null;
}

function shor(N, essais = 20) {
  for (let k = 0; k < essais; k++) {
    const a = 2 + Math.floor(Math.random() * (N - 3));
    const d = pgcd(a, N);
    if (d > 1) return { p: d, q: N / d, a, r: null, chance: true };

    const r = periode(a, N);
    if (r === null || r % 2 !== 0) continue;

    const x = puissanceMod(a, r / 2, N);
    if (x === N - 1) continue;             // cas dégénéré, on retire un a

    const p = pgcd(x - 1, N);
    const q = pgcd(x + 1, N);
    if (p > 1 && p < N) return { p, q: N / p, a, r, chance: false };
  }
  return null;
}

for (const N of [15, 21, 91, 3599]) {
  coutPeriode = 0;
  const t = shor(N);
  console.log(
    t
      ? `N = ${String(N).padStart(5)}  →  ${t.p} × ${t.q}` +
        `   (a = ${t.a}, r = ${t.r ?? "—"}, ${coutPeriode} essais de période)`
      : `N = ${N} : échec`
  );
}

const pgcd = (a, b) => (b === 0 ? a : pgcd(b, a % b));

function puissanceMod(a, x, n) {
  let r = 1n, base = BigInt(a) % BigInt(n), e = BigInt(x), m = BigInt(n);
  while (e > 0n) {
    if (e & 1n) r = (r * base) % m;
    base = (base * base) % m;
    e >>= 1n;
  }
  return Number(r);
}

let coutPeriode = 0;

function periode(a, N) {
  // La boucle qu'un ordinateur quantique n'exécute PAS. Il n'essaie pas les
  // valeurs une par une : il prépare une superposition de tous les a^x, puis
  // la transformée de Fourier quantique fait ressortir la fréquence 1/r.
  let x = a % N;
  for (let r = 1; r <= N; r++) {
    coutPeriode++;
    if (x === 1) return r;
    x = (x * a) % N;
  }
  return null;
}

function shor(N, essais = 20) {
  for (let k = 0; k < essais; k++) {
    const a = 2 + Math.floor(Math.random() * (N - 3));
    const d = pgcd(a, N);
    if (d > 1) return { p: d, q: N / d, a, r: null, chance: true };

    const r = periode(a, N);
    if (r === null || r % 2 !== 0) continue;

    const x = puissanceMod(a, r / 2, N);
    if (x === N - 1) continue;

    const p = pgcd(x - 1, N);
    const q = pgcd(x + 1, N);
    if (p > 1 && p < N) return { p, q: N / p, a, r, chance: false };
  }
  return null;
}

for (const N of [15, 21, 91, 3599]) {
  coutPeriode = 0;
  const t = shor(N);
  console.log(
    t
      ? `N = ${String(N).padStart(5)}  →  ${t.p} × ${t.q}` +
        `   (a = ${t.a}, r = ${t.r ?? "—"}, ${coutPeriode} essais de période)`
      : `N = ${N} : échec`
  );
}

// Ce qu'il faut lire dans la colonne « essais de période ».
//
// Elle croît comme N, c'est-à-dire de façon EXPONENTIELLE en le nombre de
// chiffres. Pour N = 3599 = 59 × 61, on compte déjà quelques milliers
// d'essais ; pour un module RSA de 2048 bits, ce serait de l'ordre de 2^2048.
//
// Toutes les autres lignes — pgcd, exponentiation modulaire, tirage de a —
// sont polynomiales et resteraient parfaitement praticables sur un module de
// 2048 bits. Le pgcd de deux nombres de 2048 bits prend quelques
// microsecondes.
//
// Autrement dit : RSA ne tient debout QUE parce que cette seule fonction est
// coûteuse. La transformée de Fourier quantique la rend polynomiale, et tout
// l'édifice s'effondre sans qu'aucune autre ligne n'ait besoin de changer.

À retenir

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

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

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.