Cryptographie post-quantique · C2 Réseaux euclidiens · Chapitre 4 · 5 h

ML-DSA (Dilithium) et Falcon

Fiat-Shamir avec avortements et rejet d'échantillonnage ; Falcon, NTRU et échantillonneur gaussien, et leurs compromis d'implémentation.

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.

w = A y, \qquad c = H(\mathit{message}, w), \qquad z = y + c\,s

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.

Animation · 8 étapes

Signature avec avortements : on recommence jusqu'à ce que rien ne fuie

Tour 1 — tirer le masque — y est tiré uniformément et ne sert qu'une fois. C'est lui qui masque le secret dans la réponse : réutiliser y suffirait à révéler s par simple soustraction.
Tour 1 — la réponse — z = y + c·s. Comme s est petit, z reste dans le voisinage de y — mais pas toujours assez petit.
Tour 1 — rejeté — 121 dépasse le seuil : la distribution de z dépendrait alors de s, et un attaquant qui collecte assez de signatures reconstruirait le secret. On jette TOUT, y compris c, et on recommence.
Tour 2 — nouveau masque — Un y frais, indépendant du précédent. Le rejet ne coûte rien en sécurité, seulement en temps.
Tour 2 — rejeté aussi — Encore trop grand. Le nombre de tours suit une loi géométrique : pour ML-DSA-65, l'espérance tourne autour de 4 à 5 tours.
Tour 3 — nouveau masque — Troisième tirage. Rien n'est mémorisé des tours précédents.
Tour 3 — accepté — 97 ≤ 112 : la distribution de z est désormais indépendante de s, et la preuve de sécurité peut la simuler sans connaître le secret. C'est cela, et rien d'autre, que le rejet achète.
Le coût caché — Le temps de signature est VARIABLE — trois tours ici, un seul parfois, dix parfois. Une implémentation qui laisse fuir ce nombre de tours donne à l'attaquant une information corrélée au secret : c'est le sujet du chapitre 12.

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.

Quiz · 1 question

Qu'achète exactement le rejet d'échantillonnage dans ML-DSA ?

Une signature plus courte
L'indépendance statistique entre la signature et le secret
La résistance aux collisions de la fonction de hachage

Réponse : Le rejet coûte du temps et ne gagne aucun octet. Ce qu'il garantit, c'est que la loi de z est identique quel que soit s : la preuve de sécurité peut alors simuler des signatures sans le secret, et un attaquant qui en collecte un million n'apprend rien. C'est la réponse directe à l'attaque par apprentissage du parallélépipède qui a tué NTRUSign.

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.

	ML-DSA-44	ML-DSA-65	ML-DSA-87
dimensions $(k, \ell)$	(4, 4)	(6, 5)	(8, 7)
niveau NIST	2	3	5
clé publique	1312 o	1952 o	2592 o
clé privée	2560 o	4032 o	4896 o
signature	2420 o	3309 o	4627 o

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 :

	Falcon-512	Falcon-1024
clé publique	897 o	1793 o
signature (moyenne)	≈ 666 o	≈ 1280 o

Graphique

Taille des signatures, en octets

Ed25519 : 6464
RSA-2048 : 256256
Falcon-512 : 666666
ML-DSA-44 : 24202420
ML-DSA-87 : 46274627

Falcon-512 tient en 666 octets contre 2420 pour ML-DSA-44 à sécurité comparable : un facteur 3,6. Sur une chaîne de certificats qui en porte cinq, l'écart devient décisif — et c'est exactement l'argument du chapitre 13.

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.

Quiz · 1 question

Pourquoi ML-DSA est-il recommandé par défaut alors que Falcon produit des signatures 3 à 4 fois plus courtes ?

Parce que Falcon repose sur une hypothèse jugée moins sûre
Parce que l'échantillonneur gaussien de Falcon exige du flottant double précision et est très difficile à écrire en temps constant
Parce que Falcon n'atteint pas le niveau NIST 5

Réponse : Falcon-1024 atteint bien le niveau 5, et l'hypothèse NTRU est étudiée depuis 1996. Le problème est l'implémentation : dépendre du comportement exact du flottant rend le schéma fragile d'une architecture à l'autre et exclut les plateformes sans FPU, et l'échantillonnage gaussien en temps constant a déjà donné lieu à des attaques publiées. Le NIST a privilégié ce qu'une équipe ordinaire sait implémenter sans se tromper.

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

Exercice de code

Ajoutez la condition de rejet, puis comparez les deux moyennes : sans rejet, le secret se lit dans une simple moyenne.

Point de départ

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

Solution

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

Flashcards · 3 cartes

Qu'est-ce que l'apprentissage du parallélépipède, et qu'a-t-il cassé ?: L'attaque de Nguyen et Regev (2006) contre NTRUSign. Chaque signature étant distribuée dans la cellule fondamentale de la base secrète, quelques centaines de signatures suffisaient à reconstruire cette cellule, donc la clé privée. C'est le problème auquel le rejet d'échantillonnage de ML-DSA répond.
Pourquoi la FIPS 204 fait-elle de la signature aléatoire (« couverte ») le mode par défaut ?: Une signature déterministe produit deux fois le même calcul pour le même message. Un attaquant capable d'injecter une faute peut comparer une exécution correcte et une exécution fautée et en déduire le secret. L'aléa frais rend cette comparaison impossible. Le déterminisme, vertu pour la reproductibilité, est ici une prise.
ML-DSA ou Falcon : sur quel critère choisit-on ?: Taille contre difficulté d'implémentation. Falcon-512 signe en 666 octets contre 2420 pour ML-DSA-44, ce qui compte sur une chaîne de certificats. Mais son échantillonneur gaussien exige du flottant double précision et résiste mal à l'écriture en temps constant. ML-DSA n'utilise que des entiers : c'est le choix par défaut, Falcon celui des contextes contraints en bande passante avec une équipe compétente.

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.

QCM de bloc · 12 questions

Réseaux euclidiens

1. Le déterminant d'un réseau vaut 5 pour une base donnée. Que vaut-il pour une autre base du même réseau ?

5 — c'est un invariant du réseau, pas de la base
Il dépend de la base : une base réduite donne un déterminant plus petit
5 divisé par le facteur de réduction de la nouvelle base

Réponse : La matrice de passage entre deux bases d'un même réseau est unimodulaire, de déterminant ±1 : elle préserve les volumes. Le déterminant mesure l'aire de la cellule fondamentale, donc la densité des points — une propriété de l'objet. Ce qui change d'une base à l'autre, ce sont les longueurs et les angles, et c'est précisément là-dessus que repose la trappe.

2. L'arrondi de Babai appliqué avec une base ORTHOGONALE :

échoue systématiquement, l'orthogonalité étant le pire cas
donne une approximation à un facteur 2^((n−1)/2) près
donne exactement le point du réseau le plus proche

Réponse : Avec une base orthogonale, la cellule fondamentale centrée sur un point est un pavé droit, et c'est exactement la cellule de Voronoï : le point dont la cellule contient la cible EST le plus proche. Le facteur 2^((n−1)/2) est la garantie de LLL sur la longueur du premier vecteur, une tout autre grandeur. Une base seulement réduite donne un bon résultat, pas toujours l'optimal.

3. Passer de BKZ-200 à BKZ-400 dans le modèle core-SVP classique :

double le coût de l'attaque
le multiplie par environ 2^59, pour un δ₀ qui passe de 1,0063 à 1,0040
le réduit, les blocs plus grands étant traités plus efficacement

Réponse : Le coût est 2^(0,292β) : de 2^58 à 2^117, soit un facteur 2^59. C'est tout l'intérêt du paramètre β — il achète de la qualité de réduction à un prix exponentiel. Doubler β ne double pas le coût, il l'élève au carré ; et augmenter la taille des blocs ne peut jamais coûter moins cher, puisque BKZ appelle un oracle SVP en dimension β.

4. Un collègue affirme : « les réseaux sont sûrs parce que SVP est NP-difficile ». Que corrigez-vous ?

Rien, l'énoncé est exact
SVP n'est pas NP-difficile, même dans sa version exacte
La cryptographie emploie les versions APPROCHÉES à facteur polynomial, régime où la NP-difficulté n'est ni établie ni attendue

Réponse : SVP exact est bien NP-difficile sous réductions randomisées — la deuxième option est fausse. Mais aucun schéma n'emploie SVP exact : tous reposent sur des versions approchées à facteur γ polynomial, pour lesquelles le problème tombe dans NP ∩ coNP dès γ ≥ √n. La confiance vient de quarante ans d'échecs cryptanalytiques, pas d'un théorème de complexité.

5. Pourquoi un bruit de ±1 met-il en échec l'élimination de Gauss modulo q = 3329 en dimension 768 ?

Parce que les coefficients d'élimination, de l'ordre de q, multiplient les erreurs jusqu'à dépasser q/2
Parce que la division modulaire cesse d'être définie en présence de bruit
Parce que le système devient sous-déterminé

Réponse : L'élimination ne se contente pas d'additionner les lignes : elle les combine avec des coefficients, qui multiplient les erreurs autant que les inconnues. Après 767 éliminations, le bruit cumulé dépasse q/2 et le résidu devient uniforme sur Z_q. La division modulaire reste parfaitement définie, et le système reste déterminé — c'est bien l'amplification qui détruit l'information.

6. Qu'apporte Module-LWE que Ring-LWE n'apporte pas ?

Des clés publiques nettement plus petites
Un réglage de la structure algébrique par le rang k, et un même code d'arithmétique pour tous les niveaux de sécurité
Une réduction pire cas vers cas moyen, dont Ring-LWE est dépourvu

Réponse : Ring-LWE donne déjà les clés compactes, et dispose lui aussi d'une réduction pire cas vers cas moyen. Le module apporte deux autres choses : on module la quantité de structure algébrique en jouant sur k plutôt que sur n, et surtout changer de niveau de sécurité ne change que k — l'anneau, la NTT et les tables restent identiques pour ML-KEM-512, 768 et 1024.

7. À quoi sert principalement le problème SIS ?

À accélérer la NTT
À chiffrer, en complément de LWE
À construire des signatures

Réponse : LWE cache un secret dans du bruit : c'est ce qu'il faut pour chiffrer. SIS demande d'exhiber un vecteur court non nul dans le noyau d'une matrice : c'est ce qu'il faut pour prouver qu'on sait produire quelque chose de court sans révéler comment, donc pour signer. ML-DSA repose simultanément sur les deux — Module-LWE pour cacher le secret, Module-SIS pour empêcher la forge.

8. On souhaite réduire de 10 % la taille d'un chiffré ML-KEM en compressant davantage. Quelle en est la conséquence ?

Le bruit d'arrondi augmente, se rapproche du seuil q/4, et le taux d'échec de déchiffrement monte
Aucune : la compression de ML-KEM est sans perte
La dimension du réseau sous-jacent diminue d'autant

Réponse : La compression jette des bits de poids faible : elle est délibérément avec perte, et l'erreur d'arrondi q/2^(d+1) vient s'ajouter au bruit LWE. Le déchiffrement n'est correct que tant que le total reste sous q/4. La dimension, elle, ne bouge pas — la compression ne touche qu'à l'encodage du chiffré, jamais au réseau.

9. Pourquoi le terme v est-il compressé sur 4 bits quand u l'est sur 10 ?

Parce que v contient des valeurs numériquement plus petites
Parce que v ne transporte qu'un bit de message par coefficient, décodé par comparaison à q/2
Parce que v n'intervient pas dans le déchiffrement

Réponse : Les deux termes vivent dans le même Z_q et v intervient bel et bien au déchiffrement — c'est même lui qui porte le message. Mais chacun de ses coefficients ne code qu'un bit, décodé en regardant s'il est plus près de 0 ou de q/2 : une erreur d'une centaine d'unités reste très loin du seuil. Chaque terme est compressé selon ce qu'il transporte, pas uniformément.

10. Le temps de signature de ML-DSA varie d'un message à l'autre. Est-ce normal ?

Non : c'est le signe d'une implémentation défectueuse
Oui, et c'est sans conséquence : le rejet est indépendant du secret
Oui — c'est le rejet d'échantillonnage — mais le nombre de tours est corrélé au secret et doit être masqué

Réponse : La variabilité est intrinsèque : on rejette tant que z sort de la fenêtre, et le nombre de tours suit une loi géométrique. Mais on rejette PRÉCISÉMENT parce que z, qui vaut y + c·s, a dépassé le seuil : le nombre de tours n'est donc pas indépendant du secret. Une implémentation qui laisse voir ce compte rend une information exploitable — c'est le chapitre 12.

11. Falcon-512 signe en 666 octets contre 2420 pour ML-DSA-44. Pourquoi ML-DSA reste-t-il recommandé par défaut ?

Parce que l'échantillonneur gaussien de Falcon exige du flottant double précision et résiste mal à l'écriture en temps constant
Parce que Falcon n'atteint pas le niveau NIST 5
Parce que l'hypothèse NTRU est bien plus récente que Module-LWE

Réponse : Falcon-1024 atteint le niveau 5, et NTRU date de 1996 — il est plus ancien que Module-LWE, pas plus récent. Le motif est l'implémentation : dépendre du comportement exact du flottant rend le schéma fragile d'une architecture à l'autre, exclut les plateformes sans unité flottante, et l'échantillonnage gaussien en temps constant a déjà donné lieu à des attaques publiées.

12. Que le rejet d'échantillonnage empêche-t-il ?

Les collisions de la fonction de hachage employée pour le défi
Que la loi de z dépende du secret — donc l'attaque par apprentissage du parallélépipède
Les échecs de vérification chez le destinataire

Réponse : Le rejet ne coûte aucun octet et ne gagne aucune sécurité de hachage. Ce qu'il achète est statistique : en n'acceptant z que dans une fenêtre atteignable quel que soit le secret, il rend sa loi indépendante de s. Le simulateur de la preuve peut alors produire des signatures sans connaître le secret — et un attaquant qui en collecte un million n'apprend rien, contrairement à NTRUSign.