FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG

Cet article présente le premier schéma de signature ML-DSA (FIPS 204) à seuil garantissant la confidentialité du nonce via un protocole DKG de type Shamir, permettant de générer des signatures standard de 3,3 Ko vérifiables par des implémentations non modifiées tout en éliminant l'exigence de deux parties honnêtes dans les profils coordonnés.

L'essentiel

Voici une explication simplifiée de cette recherche technique, imagée comme si nous parlions d'une coffre-fort numérique de nouvelle génération.

Le Contexte : L'Ère du "Post-Quantique"

Imaginez que vous avez un coffre-fort ultra-sécurisé pour vos secrets les plus précieux (vos clés bancaires, vos données gouvernementales). Aujourd'hui, ce coffre-fort est protégé par des serrures mathématiques classiques. Mais les scientifiques prédisent l'arrivée d'un jour où des ordinateurs "quantiques" (des machines surpuissantes) pourront forcer ces serrures en quelques secondes.

Pour contrer cela, le NIST (l'organisme américain de normalisation) a créé une nouvelle norme appelée FIPS 204 (ou ML-DSA). C'est une nouvelle serrure, basée sur des grilles mathématiques complexes, que même les ordinateurs quantiques ne pourront pas ouvrir.

Le problème : Dans le monde réel, on ne veut pas qu'une seule personne ait la clé de ce coffre-fort. Si cette personne est corrompue, perdue ou fait une erreur, tout est perdu. On veut que plusieurs personnes (disons 5) doivent se mettre d'accord pour ouvrir le coffre, mais qu'aucun groupe de 3 ne puisse le faire seul. C'est ce qu'on appelle une signature à seuil.

Le Défi : La "Serrure" est Difficile à Partager

La nouvelle serrure (ML-DSA) est très complexe. Pour signer un document, elle utilise une "clé temporaire" (appelée nonce) qui doit être parfaitement aléatoire.

• Le problème : Si on essaie de partager cette clé temporaire entre plusieurs personnes comme on partage une pizza (en coupant simplement en parts), les mathématiques de la nouvelle serrure font que le résultat final est "cassé". La signature devient invalide ou, pire, elle révèle des informations secrètes.
• L'ancien problème : Les solutions précédentes soit étaient trop lentes, soit produisaient des signatures trop grosses (comme un colis énorme au lieu d'une lettre), soit exigeaient que la majorité des participants soient honnêtes (ce qui est risqué).

La Solution Magique : Le "Partage de Shamir" et le "DKG"

L'auteur de l'article, Leo Kao, propose une méthode ingénieuse pour partager la clé temporaire sans la casser.

1. L'Analogie du Puzzle Invisible (Shamir Nonce DKG)

Imaginez que vous devez créer un nombre secret (la clé temporaire) en équipe.

• Méthode ancienne : Chacun donne un chiffre au hasard, on les additionne. Le problème ? Si un espion voit 4 chiffres sur 5, il peut déduire le 5ème.
• La méthode de l'article : Chaque participant crée une courbe mathématique invisible (un polynôme).
  • Chaque personne a un morceau de cette courbe.
  • Pour obtenir le nombre final, on doit assembler au moins 3 courbes (si le seuil est de 3).
  • Le génie : Même si un espion voit les courbes de 2 personnes, il ne peut rien deviner sur la courbe de la 3ème personne. C'est comme essayer de deviner la forme d'un puzzle en ne voyant que deux pièces : c'est impossible.
  • Résultat : La clé temporaire reste secrète, même si des espions sont dans l'équipe, et la signature finale est parfaite.

2. Le Masque "Effaceur" (Pairwise-Canceling Masks)

Parfois, les participants doivent échanger des informations intermédiaires (comme des promesses de ce qu'ils vont faire).

• L'analogie : Imaginez que chaque personne écrit un mot sur un papier, mais elle ajoute un mot de passe secret à côté.
• Le tour de passe-passe : Les mots de passe sont conçus de telle sorte que, quand on les additionne tous ensemble, ils s'annulent parfaitement (comme $+5$ et $-5$ qui font $0$).
• Résultat : Le coordinateur (celui qui assemble le tout) voit le message final, mais personne ne peut voir ce que les autres ont écrit individuellement. C'est comme si tout le monde parlait en chuchotant dans un brouillard qui s'efface une fois le message reçu.

Les Trois Scénarios d'Utilisation (Profils)

L'article propose trois façons de mettre cela en œuvre, selon le niveau de confiance dont vous disposez :

1. Profil P1 (Le Gardien de Confiance - TEE) :

   • L'idée : On utilise un coffre-fort électronique ultra-sécurisé (un TEE) qui agit comme un arbitre de confiance.
   • Avantage : C'est le plus rapide (5,8 ms !).
   • Inconvénient : Il faut faire confiance au matériel du coffre-fort.

2. Profil P2 (La Révolution Sans Confiance - MPC) :

   • L'idée : Personne n'est de confiance. Tout le monde est méfiant. On utilise des protocoles cryptographiques complexes pour que les participants calculent ensemble sans jamais se montrer leurs clés.
   • Avantage : Pas besoin de confiance matérielle. C'est la solution la plus pure mathématiquement.
   • Inconvénient : Un peu plus lent (21 ms) et plus lourd en calculs.

3. Profil P3+ (Le Mode "Demi-Asynchrone" - 2PC) :

   • L'idée : C'est fait pour les humains. Imaginez que vous devez signer un contrat important. Vous ne voulez pas attendre que 5 personnes soient en ligne en même temps.
   • Fonctionnement : Les participants préparent leurs pièces du puzzle à l'avance (quand ils sont libres). Quand le moment arrive, ils envoient juste leur pièce dans une fenêtre de temps (par exemple, dans les 5 minutes).
   • Avantage : Très flexible pour les humains, rapide (22 ms), et ne nécessite pas que tout le monde soit connecté en même temps.

Pourquoi est-ce si important ?

• Taille Standard : Contrairement aux anciennes méthodes qui produisaient des signatures géantes (17 Ko), celle-ci produit des signatures de taille normale (3,3 Ko). Cela signifie qu'on peut l'utiliser avec les logiciels existants sans rien changer.
• Sécurité Absolue : L'article prouve mathématiquement que même avec un grand nombre de participants (jusqu'à 32 ou 45), la sécurité reste intacte.
• Efficacité : Les tests montrent que cela fonctionne presque aussi vite qu'une signature classique, ce qui est un exploit pour une technologie aussi complexe.

En Résumé

Cet article présente la première méthode capable de partager la sécurité d'une clé quantique entre un grand groupe de personnes, sans que la signature finale ne soit trop lourde ni trop lente.

C'est comme si vous aviez réussi à faire en sorte que 5 gardes puissent ouvrir un coffre-fort ensemble, sans que l'un d'eux ne puisse le faire seul, et sans que le processus d'ouverture ne laisse aucune trace de leurs mouvements individuels. C'est une avancée majeure pour sécuriser l'avenir de nos données contre les ordinateurs du futur.

Résumé technique

Voici un résumé technique détaillé de l'article « FIPS 204-Compatible Threshold ML-DSA via Shamir Nonce DKG » de Leo Kao (Codebat Technologies Inc.).

1. Contexte et Problématique

L'avènement des ordinateurs quantiques menace les cryptosystèmes à clé publique actuels. En réponse, le NIST a finalisé la standardisation de ML-DSA (Module-Lattice-Based Digital Signature Algorithm) dans la norme FIPS 204. Bien que les signatures de seuil (threshold signatures) soient essentielles pour la sécurité des clés (ex: garde de crypto-monnaies, PKI distribuée), leur adaptation à ML-DSA présente des défis majeurs :

• Le paradoxe de la taille : Les schémas de seuil basés sur la structure de ML-DSA (Fiat-Shamir with Aborts) nécessitent souvent des coefficients de reconstruction de Lagrange très grands. Pour des seuils élevés ($T \ge 26$), ces coefficients dépassent le module $q$, ce qui brise la compatibilité avec le format standard de 3,3 Ko de FIPS 204 ou nécessite un "bruit" (noise flooding) qui gonfle la taille des signatures à ~17 Ko.
• La confidentialité du nonce : Dans ML-DSA, le nonce (valeur aléatoire $y$) doit être généré de manière distribuée. Les approches précédentes exigeaient souvent une hypothèse de "deux parties honnêtes" ($|S| \ge T+1$) pour garantir la confidentialité, limitant ainsi l'efficacité des protocoles.
• Le fossé de scalabilité : Il n'existait aucune solution connue permettant d'atteindre des seuils arbitraires ($T \in [9, 32]$) tout en produisant des signatures standard, vérifiables par des implémentations non modifiées, avec des taux de réussite pratiques.

2. Méthodologie et Techniques Clés

L'auteur propose Threshold ML-DSA via Shamir Nonce DKG, une première solution de seuil pour ML-DSA qui résout ces problèmes grâce à deux techniques principales :

A. DKG de Nonce par Partage de Shamir (Shamir Nonce DKG)

C'est la contribution principale. Au lieu de partager simplement le secret à long terme, les parties génèrent conjointement le nonce de signature ($y$) via un protocole de génération de clé distribuée (DKG) basé sur Shamir.

• Structure : Le nonce $y$ est généré comme un partage de Shamir de degré $(T-1)$, exactement comme le secret à long terme $s_1$.
• Calcul local : Chaque partie $i$ calcule sa réponse partielle $z_i = y_i + c \cdot s_{1,i}$ sans appliquer le coefficient de Lagrange $\lambda_i$.
• Reconstruction : Le combinateur (ou le coordinateur) agrège les réponses : $z = \sum \lambda_i z_i = \sum \lambda_i y_i + c \sum \lambda_i s_{1,i} = y + c \cdot s_1$.
• Avantage : Cela permet de maintenir la norme $\|z_i\|_\infty$ petite au niveau individuel, évitant ainsi l'explosion des coefficients. De plus, cela garantit la confidentialité du partage du nonce (nonce share privacy) par des moyens statistiques (haute entropie min-entropie conditionnelle) sans hypothèses de calcul, même avec un seul parti honnête dans les profils basés sur un coordinateur.

B. Masques à Annulation Pair-à-Pair (Pairwise-Canceling Masks)

Adaptés des schémas ECDSA, ces masques sont utilisés pour cacher les valeurs de engagement ($W_i$) et les parts de vérification $r_0$ ($V_i$).

• Fonctionnement : Chaque partie calcule un masque $m_i$ basé sur des graines PRF partagées, tel que $\sum m_i = 0$.
• Objectif : Cela permet de révéler les sommes agrégées nécessaires au protocole tout en cachant les contributions individuelles, protégeant ainsi contre la récupération de clés via les engagements masqués.

C. Distribution Irwin-Hall et Analyse de Sécurité

La somme des nonces distribués suit une distribution d'Irwin-Hall (somme de variables uniformes) plutôt qu'une distribution uniforme.

• Analyse directe : L'article utilise une analyse d'invariance par translation directe (Direct Shift-Invariance) pour quantifier la perte de sécurité. Contrairement aux bornes conservatrices (style Raccoon) qui deviennent nulles pour un grand nombre de sessions, cette analyse montre que la perte de sécurité est inférieure à 0,013 bits par session pour des seuils jusqu'à 33. Cela élimine le problème de scalabilité de sécurité trouvé dans les travaux antérieurs.

3. Profils de Déploiement

L'article présente trois profils de déploiement avec des preuves de sécurité UC (Universal Composability) complètes :

1. Profil P1 (Assisté par TEE) : Utilise un coordinateur dans un environnement d'exécution de confiance (TEE/HSM).
   • Avantages : 3 tours en ligne, latence très faible (5,8 ms pour 3-of-5), confidentialité statistique du nonce avec $|S|=T$.
   • Confiance : Basée sur l'intégrité du matériel TEE.
2. Profil P2 (Totalement Distribué / MPC) : Aucun coordinateur de confiance ; utilise le calcul multipartite sécurisé (MPC) avec SPDZ et edaBits.
   • Avantages : Sécurité contre une majorité de parties corrompues (dishonest-majority), 5 tours en ligne, aucune confiance matérielle.
   • Coût : Latence plus élevée (~22 ms pour 3-of-5, jusqu'à 194 ms pour des seuils plus grands).
3. Profil P3+ (2PC Semi-Asynchrone) : Conçu pour les autorisations humaines (human-in-the-loop). Deux parties de calcul (CP) effectuent la vérification $r_0$ via un 2PC, tandis que les signataires pré-calculent les nonces hors ligne et répondent dans une fenêtre de temps.
   • Avantages : 2 tours logiques, latence faible (~22 ms), adapté aux scénarios asynchrones.

4. Résultats et Performances

L'implémentation en Rust (disponible pour publication) a été benchmarkée sur du matériel grand public (Intel i7-12700H) :

• Compatibilité : Les signatures générées sont byte-identiques aux signatures ML-DSA standard (3,3 Ko pour ML-DSA-65) et sont vérifiables par n'importe quelle implémentation FIPS 204 non modifiée.
• Taux de réussite : Le taux de réussite par tentative est d'environ 21 % à 45 %, comparable (et parfois supérieur) au cas d'un seul signataire (~20-25 %). La distribution d'Irwin-Hall concentre plus de nonces dans la région d'acceptation.
• Latence :
  • P1 (TEE) : 4 ms à 60 ms (selon le seuil).
  • P2 (MPC) : 21 ms à 194 ms.
  • P3+ (2PC) : 17 ms à 94 ms.
• Scalabilité : Le système fonctionne efficacement jusqu'à des seuils de 32 sur 45 parties.

5. Signification et Impact

Ce travail comble un vide critique dans la cryptographie post-quantique :

1. Première solution de seuil FIPS 204 : C'est la première implémentation de seuil pour ML-DSA qui produit des signatures standard de taille fixe, rendant le déploiement "plug-and-play" possible.
2. Suppression de l'hypothèse "Deux Honnêtes" : Grâce au DKG de nonce par Shamir, le protocole fonctionne avec $|S|=T$ (le minimum théorique) dans les profils à coordinateur, améliorant l'efficacité par rapport aux schémas précédents.
3. Sécurité prouvée et scalable : L'analyse de sécurité directe réfute les craintes selon lesquelles la distribution non-uniforme des nonces rendrait le système vulnérable à grande échelle. La perte de sécurité est négligeable (< 0,013 bits/session).
4. Flexibilité de déploiement : En offrant trois profils (TEE, MPC pur, 2PC semi-asynchrone), l'article répond aux besoins variés des industries (banque, gouvernement, crypto), permettant un équilibre entre confiance matérielle, sécurité cryptographique pure et latence.

En résumé, cet article fournit les fondations théoriques et pratiques pour déployer des infrastructures à clé publique (PKI) et des systèmes de garde de clés résistants aux attaques quantiques, tout en respectant strictement les normes NIST/FIPS 204.