Article : Blockstream Team
Compilation : Saoirse, Foresight News
Blockstream Research a publié un rapport complet sur les signatures basées sur les réseaux euclidiens pour le Bitcoin. Cet article résume le contenu de la recherche, les découvertes clés et les recommandations associées. Le rapport complet est accessible via le lien.
Les signatures numériques sont le mécanisme central d'autorisation des transactions Bitcoin. Les signatures Schnorr et ECDSA, qui assurent cette fonction aujourd'hui, sont extrêmement peu coûteuses. En 1994, Shor a prouvé qu'un ordinateur quantique suffisamment puissant pourrait casser ces deux types de signatures. Bien que le moment où une telle machine pourra être construite fasse l'objet de vifs débats, il est nécessaire d'établir un plan de déploiement viable pour des signatures post-quantiques avant que le problème ne se pose réellement.
Les schémas de signature basés sur les réseaux euclidiens sont des candidats populaires pour remplacer les signatures actuelles. La cryptographie basée sur les réseaux a une histoire de recherche de plus d'un siècle, et ses applications cryptographiques se développent depuis près de trente ans. Dans le paysage de la cryptographie post-quantique, les signatures basées sur les réseaux offrent plusieurs avantages : la taille totale de la clé publique et de la signature peut être inférieure à 1,6 kilo-octets, et leur structure algébrique pourrait potentiellement prendre en charge à l'avenir les signatures multiples, les signatures à seuil et les preuves succinctes.
Ce rapport étudie trois schémas : Dilithium, Falcon et Hawk. À l'intention des lecteurs peu familiers avec la cryptographie basée sur les réseaux, nous expliquons la logique de conception de chaque schéma, présentons en détail leurs algorithmes, et analysons leur sécurité, leurs performances et leur déploiement pratique (par exemple, la dérivation de clés dans les portefeuilles). Parmi ces trois, quels schémas peuvent réellement être déployés sur la blockchain Bitcoin ?
Dimensions d'évaluation
Le choix d'un schéma de signature pour Bitcoin est soumis à ses propres contraintes. Cette évaluation s'articule autour de quatre critères principaux :
- Coût sur la chaîne : L'une des métriques les plus importantes est la taille totale de la clé publique et de la signature. Lorsqu'une sortie est dépensée, la clé publique et la signature sont enregistrées sur la chaîne, et les nœuds complets doivent télécharger et stocker chaque octet. Le coût de vérification est également crucial : chaque signature doit être vérifiée par tous les nœuds du réseau. Une vérification lente imposerait un fardeau à l'ensemble du réseau.
- Complexité de mise en œuvre : La capacité à implémenter un schéma en toute sécurité est essentielle. Si la conception nécessite des calculs en virgule flottante ou un échantillonnage gaussien précis, une erreur d'implémentation ou une attaque par canal auxiliaire comme l'analyse temporelle pourrait révéler la clé privée. La complexité de mise en œuvre est un facteur à ne pas négliger pour une transition en douceur.
- Risques de déploiement : L'intégration pratique dans Bitcoin rencontre divers obstacles réels : le choix de la fonction de hachage au niveau du consensus (la plupart des schémas candidats utilisent SHAKE, tandis que Bitcoin utilise SHA-256), la reproductibilité des signatures sur différentes plateformes, et l'adaptation des procédures de signature aux limites de mémoire des portefeuilles matériels.
- Potentiel d'évolution : La grande majorité des portefeuilles Bitcoin utilisent le mécanisme hiérarchique déterministe BIP-32 : à partir d'une seule clé publique maîtresse, il est possible de dériver un nombre infini de clés publiques enfants sans jamais toucher la clé privée. Aucun des schémas de signature post-quantiques standardisés ne prend en charge nativement cette fonctionnalité. Nous étudions donc le coût pour ajouter cette capacité, et examinons également diverses variantes non standard qui pourraient offrir des avantages supplémentaires.
Quel niveau de sécurité choisir ?
Avant de comparer les tailles, il faut déterminer le niveau de sécurité cible, un choix moins simple qu'il n'y paraît. Le NIST divise les niveaux de sécurité en 1 à 5 ; plus le niveau est élevé, plus la sécurité est forte, mais plus la taille des clés et des signatures est importante.
Nous estimons que Bitcoin devrait adopter au moins le niveau de sécurité 3. Une sortie Bitcoin peut rester non dépensée pendant des décennies. Si les progrès en cryptanalyse réduisent le niveau de sécurité réel du schéma, les actifs resteront bloqués par des clés affaiblies, exposés à long terme au risque. Les hypothèses de la cryptographie basée sur les réseaux ont été soumises à près de trente ans de cryptanalyse publique, soit plus longtemps que les courbes elliptiques adoptées par Bitcoin. Cependant, la structure algébrique complexe des réseaux laisse encore de nombreuses opportunités pour de futures attaques. Nous ne devrions pas parier toute la sécurité à long terme sur ces hypothèses.
Les principaux produits grand public ont fait le même choix. Le protocole PQ3 d'iMessage d'Apple évite complètement les paramètres de niveau 1 pour les réseaux, utilisant exclusivement les niveaux 3 et 5 ; Cloudflare utilise ML-KEM-768 (niveau 3) dans son déploiement TLS post-quantique, indiquant que si le niveau 1 semble sûr aujourd'hui, il faut prévoir une marge de sécurité pour les décennies à venir de cryptanalyse. L'horizon temporel de sécurité de Bitcoin est encore plus long que ces deux exemples.
Augmenter le niveau de sécurité a un coût. Par exemple, passer de Dilithium niveau 2 à niveau 3 augmente la taille totale d'environ 1,5 kilo-octet. Le rapport compare tous les ensembles de paramètres pour tous les niveaux de sécurité, permettant au lecteur de faire son propre arbitrage. L'exemple de Hawk montre que ces considérations de sécurité prudentes ne sont pas purement théoriques.
Détail des schémas candidats
Dilithium : Un schéma à la conception simple
Dilithium a été normalisé par le NIST sous le nom de ML-DSA dans la norme FIPS 204. Il transpose le paradigme engagement-défi-réponse de la signature Schnorr dans l'arithmétique des réseaux modulaires.
Sa plus grande caractéristique est sa simplicité. Tous les calculs de Dilithium sont des opérations sur des entiers : opérations d'anneau, multiplications matrice-vecteur, hachage, arrondi. Pas de calculs en virgule flottante, pas d'échantillonnage gaussien discret. Il est plus facile d'écrire une implémentation sécurisée et à temps constant. C'est aussi le candidat le plus largement déployé, déjà intégré dans OpenSSL, BoringSSL, AWS-LC et Apple CryptoKit.
Le prix à payer est une taille importante. ML-DSA-65 de niveau 3 a une clé publique de 1952 octets, une signature de 3309 octets, pour un total de 5261 octets, soit environ 55 fois la taille totale des paires de clés et signatures natives de Bitcoin. C'est le plus volumineux des trois schémas à niveau de sécurité équivalent.
Le point le plus précieux de Dilithium pour Bitcoin est qu'il est le seul des trois à s'approcher de la mise en œuvre d'une dérivation de clés de style BIP-32. La construction de clés re-randomisables DilithiumRK permet de générer des clés enfants à partir d'une clé parent uniquement avec des informations publiques. Le rapport analyse trois variantes, dont notre proposition DilithiumRKS, où la logique de dérivation est entièrement gérée par le logiciel du portefeuille, la chaîne n'ayant besoin que d'un vérificateur standard pour traiter des signatures ML-DSA ordinaires. Cependant, aucune n'est encore prête pour le déploiement : deux variantes nécessitent de modifier le vérificateur, DilithiumRKS lui-même manque d'une preuve complète d'inforgeabilité ; tous les schémas dépendent d'une matrice partagée par tous les utilisateurs, ce qui, bien que formellement sûr sous l'hypothèse Module-LWE, lie la sécurité de toutes les clés à une seule instance. Nous considérons que la dérivation de clés publiques basée sur Dilithium n'est, à ce stade, qu'une preuve de concept, non déployable en pratique.
Falcon : Un schéma compact
Falcon a été sélectionné par le NIST, son nom de standardisation est FN-DSA. C'est le plus compact des trois. Falcon-512 de niveau 1 a une taille totale (clé publique + signature) de 1563 octets ; Falcon-1024 de niveau 5 totalise 3073 octets. Falcon-1024, avec une marge de sécurité plus élevée, est même plus petit que Dilithium de niveau 3.
Falcon adopte une approche différente de Dilithium : un schéma de hachage puis signature basé sur le réseau NTRU. La clé privée du signataire est une base courte du réseau ; le message est haché et mappé en un point de l'espace, le signataire utilise la base courte pour trouver un vecteur du réseau proche de ce point. Le point et ce vecteur proche constituent ensemble la signature ; la vérification consiste seulement à vérifier que le vecteur appartient au réseau et qu'il est suffisamment proche. La difficulté de mise en œuvre est de trouver le vecteur sans révéler d'information sur la base. Les premiers schémes GGH et NTRUSign prenaient simplement le point du réseau le plus proche, révélant ainsi une partie de l'information géométrique à chaque signature. Falcon utilise le cadre GPV, échantillonnant le vecteur proche à partir d'une distribution gaussienne, prouvant que la sortie de l'échantillonnage est indépendante de la base, éliminant le risque de fuite, mais la complexité de l'implémentation de l'échantillonneur augmente considérablement.
L'échantillonneur est le point faible de Falcon au niveau de l'ingénierie. Il opère dans le domaine de Fourier complexe et nécessite des calculs en virgule flottante. Différents processeurs, compilateurs et options de compilation peuvent entraîner des résultats flottants incohérents. Ce n'est pas seulement un problème de compatibilité, c'est un risque de sécurité : la preuve de sécurité GPV exige que pour un même condensé, le signataire ne produise jamais deux vecteurs courts différents ; une fois la signature rendue déterministe, les différences d'arrondi flottant dues à la plateforme briseraient cette condition. Des solutions existent : un Falcon déterministe peut simuler des entiers pour remplacer les flottants matériels, produisant des signatures identiques sur toutes les plateformes. Le coût est une vitesse de signature environ 15 fois plus lente, et une génération de clés environ 2 fois plus lente.
Il est important de noter que l'étape de vérification n'est pas affectée : la vérification de Falcon utilise entièrement des opérations sur des entiers, avec un résultat déterministe, et c'est aussi la plus rapide parmi les candidats. Cette asymétrie est très favorable à Bitcoin : la signature est exécutée une fois par le portefeuille lors de la création de la transaction de dépense, tandis que chaque signature doit être vérifiée par tous les nœuds complets du réseau. Rendre la signature 15 fois plus lente est une dépense à faible fréquence, et en échange d'une reproductibilité multiplateforme et de calculs entiers, cela nous semble un compromis raisonnable. Ainsi, le problème des flottants est un obstacle résoluble par des moyens techniques, et non une faille fatale.
Deux points à noter : En raison de contraintes structurelles, Falcon n'a pas de paramètres de niveau 3, seulement niveau 1 ou 5. Pour des raisons de marge de sécurité, nous recommandons Falcon-1024. Deuxièmement, la signature consomme beaucoup de mémoire : l'échantillonneur pour l'ensemble de paramètres 1024 dépend d'un arbre précalculé occupant environ 90 kilo-octets. Les portefeuilles matériels peuvent reconstruire cet arbre dynamiquement branche par branche, réduisant l'empreinte mémoire à 16 kilo-octets, mais doublant le temps de signature. Un ralentissement de la signature sur le matériel est un coût réel, mais acceptable.
Hawk : Un schéma qui a échoué
L'objectif de Hawk était de combiner les avantages des deux autres schémas : la signature Hawk-512 fait seulement 555 octets, plus petite que Falcon ; la signature utilise uniquement des opérations sur des entiers, avec une empreinte mémoire minimale de seulement 6 kilo-octets. C'était également le seul candidat basé sur les réseaux restant au troisième tour de la compétition de signatures supplémentaires du NIST, et le rapport lui consacre une grande partie.
Le prix à payer concerne les hypothèses de sécurité. Il ne s'appuie pas sur les problèmes NTRU et SIS, testés par des décennies de cryptanalyse, mais sur le problème d'isomorphisme de réseaux et l'hypothèse one-more-SVP, dont l'histoire de recherche est relativement plus courte.
Juste avant la finalisation du rapport, Straznickas et Weis d'Anthropic ont découvert une faille structurelle dans la construction du réseau de Hawk : la dimension réelle du problème SVP à résoudre pour récupérer la clé n'était que la moitié de celle prévue par les concepteurs. La sécurité en bits de récupération de clé pour les paramètres candidats a été considérablement affaiblie. Les chercheurs ont effectué une attaque complète de bout en bout pour récupérer la clé sur les paramètres de défi HAWK-256 utilisés pour l'analyse cryptographique ; même après l'attaque, les propositions officielles HAWK-512 et HAWK-1024 restaient impossibles à casser en pratique. L'équipe Hawk a confirmé l'efficacité de l'attaque et a retiré le schéma du processus du NIST ; l'équipe a indiqué que si le bug était corrigé en doublant les paramètres, l'avantage de taille, dont Hawk était fier, disparaîtrait complètement.
Le rapport conserve néanmoins les sections sur Hawk, car cette attaque cible des propriétés algébriques spécifiques au corps de nombres, et ne rejette pas entièrement ce paradigme de conception. On ne sait pas encore si une nouvelle conception pourrait éviter la faille. L'incident Hawk illustre également de manière tangible la raison de notre insistance sur une marge de sécurité conservatrice : un schéma, même excellent en taille, rapide, et ayant passé plusieurs tours de standardisation, peut voir son niveau de sécurité estimé chuter considérablement à cause d'un seul article.
Tableau comparatif des schémas
Tous les schémas du tableau ci-dessus (y compris SPHINCS+) sont des signatures sans état : le signataire n'a pas besoin de garder un historique des signatures. Les signatures basées sur le hachage avec état comme XMSS peuvent avoir des signatures encore plus petites, mais nécessitent de maintenir un état de signature ; vous pouvez consulter le rapport spécial sur les signatures basées sur le hachage pour une comparaison.
De nombreux obstacles persistent pour le déploiement
Falcon manque d'un schéma de dérivation de clés utilisable. La seule proposition publique actuelle d'un schéma de dérivation de style BIP-32 pour Falcon re-randomise la base de la clé privée, ce qui fait exploser la norme limite de la signature, faisant gonfler la signature sur la chaîne à environ 23,7 kilo-octets. De plus, les paramètres de cette proposition ne satisfont pas ses propres conditions de sécurité, et si ce problème était corrigé, la taille augmenterait encore davantage. Il n'existe actuellement aucune implémentation viable de dérivation de clés publiques pour Falcon, ce qui est également le problème ouvert le plus précieux identifié dans le rapport.
La norme Falcon n'est pas encore finalisée. Bien que le NIST ait sélectionné Falcon, le projet de norme FN-DSA n'est pas encore officiellement publié. Ce n'est qu'après la finalisation de la normalisation que des implémentations auditées, des vecteurs de test et un support matériel émergeront. Un déploiement large réduirait les risques et la difficulté de l'intégration au niveau du consensus de Bitcoin. Nous recommandons d'attendre la publication officielle de FN-DSA, avant cela, Falcon est encore sujet à des modifications.
La variante Falcon-WS : Cette variante assouplit les paramètres internes, en compensant par un échantillonnage par rejet, réduisant la taille totale à 1114 octets pour le niveau 1 et à 2387 octets pour le niveau 5, soit une réduction supplémentaire par rapport à la version originale de Falcon. Cette direction a une valeur de recherche, mais ne sera pas incluse dans la norme officielle et nécessite plus de validation par la cryptanalyse. Des recherches ont déjà révélé une faille dans la preuve d'inforgeabilité forte d'un schéma dérivé (l'inforgeabilité normale n'est pas affectée).
Un schéma plus performant apparaîtra-t-il à l'avenir ? Outre les schémas ci-dessus, la série Fiat-Shamir remonte au BLISS de 2013 ; la dernière proposition de Gärtner à la conférence CRYPTO 2025, basée sur des hypothèses matures, a des tailles théoriques comparables à Falcon. La difficulté fondamentale de cette série pour le déploiement technique est la sécurité de l'implémentation : BLISS a été cassé par des canaux auxiliaires en raison d'un échantillonnage gaussien non constant dans le temps ; les schémas ultérieurs n'ont pas complètement résolu ce problème, et la dernière proposition indique également une difficulté accrue de protection lors de l'échantillonnage. Tant que ce problème n'est pas résolu, ces schémas n'ont qu'un intérêt théorique et ne conviennent pas au déploiement.
Les signatures basées sur les réseaux et sur le hachage peuvent être complémentaires. Les signatures basées sur les réseaux peuvent être un composant dans des schémas hybrides. Par exemple, dans SHRINCS, le chemin de récupération sans état utilise actuellement une signature SPHINCS+ de plusieurs kilo-octets ; le remplacer par une signature Falcon (ou Falcon-WS) offrirait une taille plus petite et une vérification plus rapide, réduisant considérablement le coût du chemin de récupération à faible fréquence, sans affecter le chemin d'utilisation quotidienne.
Conclusion de la recherche
Le classement des schémas candidats basés sur les réseaux est très clair : Hawk est éliminé après l'attaque de l'équipe d'Anthropic ; Dilithium est le plus facile à implémenter et le seul ayant une base de recherche sur la dérivation de clés, mais sa taille est peu favorable au coût sur la chaîne Bitcoin ; Falcon combine une taille compacte, une vérification rapide et des hypothèses de sécurité matures ; son principal point faible – les calculs en virgule flottante côté signature – dispose déjà de solutions techniques viables. Si nous devions choisir aujourd'hui un schéma de signature basé sur les réseaux pour Bitcoin, nous opterions pour Falcon-1024.
À l'heure actuelle, notre position reste la même que dans le rapport sur les signatures basées sur le hachage : la voie conservatrice à court terme reste les signatures basées sur le hachage, dont les hypothèses de sécurité sont les plus matures et les risques les plus faibles, ce qui les rend appropriées comme solution de transition. Une fois que FN-DSA sera finalisé, avec des spécifications stables, des bibliothèques de code auditées et un support des portefeuilles matériels, Falcon offrira une amélioration significative par rapport aux signatures purement basées sur le hachage ; un déploiement hybride peut également être envisagé, permettant aux deux systèmes de signatures de se compléter.
