ML-DSA (Dilithium) et Falcon

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

À 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.