Comment Bitcoin peut-il résister aux ordinateurs quantiques ? Comparaison de trois schémas de signature sur réseaux

Auteur original : Blockstream Team

Compilation originale : Saoirse, Foresight News

Blockstream Research a publié un rapport de recherche complet sur les signatures sur réseaux pour Bitcoin. Cet article résume le contenu de la recherche, les principales conclusions et les recommandations associées. Le rapport complet est accessible ici.

Les signatures numériques sont le mécanisme central pour autoriser les transactions Bitcoin, et les signatures Schnorr et ECDSA actuellement utilisées à cette fin 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 débat se poursuive sur la date à laquelle de telles machines seront disponibles, nous devons élaborer un plan de déploiement viable de signatures post-quantiques avant que le problème ne survienne réellement.

Les schémas de signature sur réseaux sont un candidat populaire pour remplacer les signatures existantes. La cryptographie sur réseaux a une histoire de recherche de plus d'un siècle, et ses applications cryptographiques sont développées depuis près de trois décennies. En cryptographie post-quantique, les signatures sur réseaux offrent plusieurs avantages : la taille totale des clés publiques et des signatures peut être inférieure à 1,6 kilo-octet, et leur structure algébrique est prometteuse pour prendre en charge à l'avenir les multisignatures, les signatures à seuil et les preuves succinctes.

Ce rapport étudie trois schémas : Dilithium, Falcon et Hawk. Pour les lecteurs peu familiers avec la cryptographie sur réseaux, nous expliquons la logique de conception de chaque schéma, fournissons une description complète du déroulement de l'algorithme et les analysons selon des dimensions telles que la sécurité, les performances et le déploiement pratique (par exemple, la dérivation de clés de portefeuille). Parmi les trois, quels schémas peuvent réellement être déployés sur la blockchain Bitcoin ?

Critères d'évaluation

Bitcoin a ses propres contraintes quant au choix du schéma de signature, et cette évaluation se concentre sur quatre critères fondamentaux :

• Coût sur la chaîne : L'une des mesures les plus importantes est la taille totale des clés publiques et des signatures. Lorsqu'une sortie est dépensée, la clé publique et la signature sont toutes deux 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 tout aussi critique : chaque signature est vérifiée par tous les nœuds du réseau, et une vérification lente pèserait sur l'ensemble du réseau.
• Complexité de mise en œuvre : La possibilité de mettre en œuvre le schéma de manière sécurisée est cruciale. Si la conception nécessite de l'arithmétique à virgule flottante ou un échantillonnage gaussien délicat, une erreur d'implémentation ou une attaque par canal auxiliaire telle que l'analyse temporelle pourrait divulguer la clé. Pour parvenir à une migration en douceur, la complexité de mise en œuvre est un facteur à ne pas négliger.
• Risque de déploiement : Lors de l'intégration réelle dans Bitcoin, divers obstacles pratiques se présentent : le choix de la fonction de hachage au niveau du consensus (la plupart des candidats utilisent SHAKE, tandis que Bitcoin utilise SHA-256), la reproductibilité des résultats de signature entre les plateformes, et la compatibilité de la procédure de signature avec les contraintes de mémoire des portefeuilles matériels.
• Potentiel de développement : La grande majorité des portefeuilles Bitcoin utilisent le mécanisme déterministe hiérarchique BIP-32 : à partir d'une seule clé publique maîtresse, un nombre infini de clés publiques enfants peut être dérivé sans accès à la clé privée. Actuellement, aucun schéma de signature post-quantique standardisé ne prend en charge nativement cette fonctionnalité ; nous étudions donc le coût de l'ajout de cette capacité, et examinons également diverses variantes non standard du schéma qui pourraient offrir des avantages supplémentaires.

Quel niveau de sécurité choisir ?

Avant de comparer les tailles, nous devons d'abord déterminer le niveau de sécurité cible, et ce choix n'est pas aussi simple qu'il n'y paraît. Le NIST classe les niveaux de sécurité de 1 à 5 ; les niveaux supérieurs offrent une sécurité plus forte mais aussi des tailles de clés et de signatures plus grandes.

Nous pensons que Bitcoin devrait adopter au moins le niveau de sécurité 3. Les sorties Bitcoin peuvent rester non dépensées pendant des décennies, et si les progrès de la cryptanalyse réduisent le niveau de sécurité réel du schéma, les actifs seraient verrouillés par des clés affaiblies et exposés à un risque à long terme. Les hypothèses sur réseaux ont déjà résisté à près de trois décennies de cryptanalyse publique, soit plus longtemps que les fondements de la recherche lorsque Bitcoin a adopté les courbes elliptiques. Cependant, la structure algébrique complexe de la cryptographie sur réseaux laisse encore de nombreuses voies d'attaque futures, et nous ne devrions pas miser toute notre sécurité à long terme sur elle.

Les principaux produits grand public ont porté le même jugement. Le protocole PQ3 d'iMessage d'Apple écarte directement les paramètres de réseau de niveau 1 et utilise partout des paramètres de niveau 3 et de niveau 5 ; Cloudflare utilise ML-KEM-768 (niveau 3) dans son déploiement TLS post-quantique, déclarant que si le niveau 1 semble actuellement sûr, il est nécessaire de réserver une marge de sécurité pour des décennies de cryptanalyse future. L'horizon temporel de sécurité de Bitcoin est encore plus long que les deux.

Augmenter le niveau de sécurité a un coût. Par exemple, passer Dilithium du niveau 2 au niveau 3 augmente la taille totale d'environ 1,5 kilo-octet. Le rapport compare les jeux de paramètres à tous les niveaux de sécurité, permettant aux lecteurs de peser eux-mêmes les compromis. Le cas de Hawk prouve que les considérations de sécurité conservatrices ne sont pas purement théoriques.

Analyse détaillée des schémas candidats

Dilithium : une conception simple

Dilithium, normalisé par le NIST sous le nom de ML-DSA dans FIPS 204, transpose le paradigme engagement-défi-réponse des signatures Schnorr à l'arithmétique des réseaux modulaires.

Sa plus grande caractéristique est la simplicité. Toutes les opérations de Dilithium sont des opérations sur entiers : opérations d'anneau, multiplication matrice-vecteur, hachage et arrondi. Il n'y a pas d'arithmétique à virgule flottante ni d'échantillonnage gaussien discret. Il est plus facile d'écrire des implémentations sécurisées à 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 compromis est une taille plus grande. Au niveau de sécurité 3, ML-DSA-65 a une clé publique de 1952 octets et une signature de 3309 octets, soit un total de 5261 octets, environ 55 fois la taille totale de la clé publique/privée et de la signature natives de Bitcoin, ce qui en fait le plus grand des trois schémas au même niveau de sécurité.

Pour Bitcoin, l'aspect le plus précieux de Dilithium est qu'il est le seul des trois à se rapprocher de la mise en œuvre d'une dérivation de clés de type BIP-32. La construction de clé re-randomisable DilithiumRK peut générer des clés enfants à partir de clés parentes en utilisant uniquement des informations publiques. Le rapport analyse trois variantes, dont notre proposition DilithiumRKS, où la logique de dérivation est entièrement dans le logiciel du portefeuille et la chaîne ne nécessite qu'un vérificateur standard pour traiter les signatures ML-DSA ordinaires. Cependant, aucune des trois n'est prête pour la production : deux variantes nécessitent des modifications du vérificateur, et DilithiumRKS lui-même manque d'une preuve complète d'infalsifiabilité ; tous les schémas reposent sur une matrice partagée à l'échelle du réseau, ce qui est formellement sûr sous l'hypothèse Module-LWE mais lie la sécurité de toutes les clés à une seule instance. Nous pensons que la dérivation de clés publiques basée sur Dilithium n'est actuellement qu'une preuve de concept et ne peut pas être déployée en pratique.

Falcon : un schéma compact

Falcon, sélectionné par le NIST et normalisé sous le nom de FN-DSA, est le plus compact des trois. Au niveau de sécurité 1, Falcon-512 a une taille combinée de clé publique et de signature de 1563 octets ; au niveau 5, Falcon-1024 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 paradigme hachage-puis-signature basé sur les réseaux NTRU. La clé privée du signataire est une base courte du réseau ; le message est haché en un point de l'espace, et le signataire utilise la base courte pour trouver un vecteur du réseau proche de ce point. Le point et le vecteur proche forment ensemble la signature ; la vérification se contente de contrôler que le vecteur appartient au réseau et qu'il est suffisamment proche. Le défi de mise en œuvre est de trouver le vecteur sans divulguer d'informations sur la base. Les premiers schémas GGH et NTRUSign sélectionnaient directement des points proches du réseau, divulguant des informations géométriques à chaque signature. Falcon adopte le cadre GPV, échantillonnant des vecteurs proches à partir d'une distribution gaussienne, ce qui rend prouvablement la sortie échantillonnée indépendante de la base, éliminant le risque de fuite, mais la difficulté de mise en œuvre de l'échantillonneur augmente considérablement.

L'échantillonneur est le point faible technique de Falcon. Il opère dans le domaine de Fourier complexe et nécessite des calculs à virgule flottante. Différents processeurs, compilateurs et options d'optimisation de compilation peuvent entraîner des résultats à virgule flottante incohérents. Ce n'est pas seulement un problème de compatibilité, mais aussi un problème de sécurité : la preuve de sécurité GPV exige que le signataire ne produise jamais deux vecteurs courts différents pour le même condensé ; si la signature devient déterministe, les différences d'arrondi à virgule flottante induites par la plateforme violeraient cette condition. Il existe une solution viable : Falcon déterministe peut remplacer la virgule flottante matérielle par une émulation entière, produisant des signatures identiques sur toutes les plateformes. Le coût est un ralentissement d'environ 15 fois de la vitesse de signature et d'environ 2 fois de la génération de clés.

Il est important de noter que la vérification n'est pas affectée : la vérification de Falcon est entièrement basée sur des entiers, déterministe, et aussi la plus rapide parmi les candidats. Cette propriété asymétrique est très favorable à Bitcoin : la signature est effectuée une fois par le portefeuille lors de la dépense d'une transaction, tandis que chaque signature est vérifiée par tous les nœuds complets du réseau. Un ralentissement de 15 fois de la signature est un coût à faible fréquence, et en échange nous obtenons la reproductibilité multiplateforme et l'arithmétique entière, ce que nous considérons comme un compromis raisonnable. Par conséquent, le problème de la virgule flottante est un obstacle qui peut être résolu par des moyens techniques, et non un défaut fatal.

Deux points à noter : en raison de contraintes structurelles, Falcon n'a pas de paramètres de niveau 3 ; il faut choisir soit le niveau 1, soit le niveau 5. Sur la base de considérations de marge de sécurité, nous recommandons Falcon-1024. Deuxièmement, la signature consomme une grande quantité de mémoire : l'échantillonneur pour le jeu de paramètres 1024 repose sur un arbre précalculé, occupant environ 90 kilo-octets de mémoire. Les portefeuilles matériels peuvent reconstruire dynamiquement l'arbre branche par branche, réduisant l'utilisation de la mémoire à 16 kilo-octets, mais le temps de signature double. Une signature plus lente sur les appareils matériels est un coût réel, mais reste acceptable.

Hawk : un schéma en échec

Hawk visait à combiner les avantages des deux autres schémas : les signatures Hawk-512 ne font que 555 octets, plus petites que Falcon ; la signature est entièrement basée sur des entiers, avec une empreinte mémoire minimale de seulement 6 kilo-octets. C'était aussi le seul candidat sur réseaux restant au troisième tour de la compétition de signatures supplémentaires du NIST, et le rapport consacre un espace considérable à ce schéma.

Le compromis réside dans les hypothèses de sécurité. Il ne repose pas sur les problèmes NTRU ou SIS qui ont été soumis à des décennies de cryptanalyse, mais sur le problème d'isomorphisme des réseaux et l'hypothèse one-more-SVP, dont l'histoire de recherche est relativement courte.

Juste avant la finalisation du rapport, Straznickas et Weis d'Anthropic ont découvert un défaut structurel dans la construction de réseau de Hawk : la dimension du problème SVP qui doit réellement être résolu pour la récupération de clé n'est que la moitié de ce que les concepteurs avaient prévu. Les bits de sécurité de récupération de clé des jeux de paramètres candidats ont été considérablement affaiblis. Les chercheurs ont réalisé une attaque complète de bout en bout de récupération de clé sur le paramètre de défi HAWK-256 utilisé pour la cryptanalyse ; même sous attaque, les HAWK-512 et HAWK-1024 formellement proposés restent pratiquement incassables. L'équipe Hawk a confirmé la validité de l'attaque et a retiré le schéma du processus du NIST ; l'équipe a déclaré que si la vulnérabilité était corrigée en doublant les paramètres, l'avantage de taille initial de Hawk disparaîtrait complètement.

Le rapport conserve la section Hawk car l'attaque cible des propriétés algébriques d'un corps de nombres spécifique et ne nie pas entièrement le paradigme de conception. La question de savoir si une refonte peut éviter la vulnérabilité reste ouverte. L'incident Hawk valide également intuitivement notre insistance sur des marges de sécurité conservatrices : un schéma avec une taille et une vitesse excellentes, ayant passé plusieurs cycles de normalisation, peut voir son niveau de sécurité estimé drastiquement réduit par 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 d'enregistrer les signatures passées. Les signatures à base de hachage avec état comme XMSS peuvent atteindre des tailles de signature plus petites mais nécessitent de maintenir l'état de signature ; voir le rapport spécial sur les signatures à base de hachage pour comparaison.

De nombreux obstacles subsistent pour le déploiement

Falcon ne dispose pas d'un schéma de dérivation de clés utilisable. Le seul schéma de dérivation de type BIP-32 publiquement disponible pour Falcon re-randomise la base de la clé privée, ce qui entraîne une augmentation drastique de la borne supérieure de la norme de signature, et les signatures sur la chaîne gonflent jusqu'à environ 23,7 kilo-octets. De plus, les paramètres du schéma ne satisfont pas leurs propres conditions de sécurité, et corriger ce problème augmenterait encore la taille. Il n'existe actuellement aucune implémentation viable de dérivation de clé publique Falcon, ce qui est aussi 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 FN-DSA n'a pas été officiellement publié. Ce n'est qu'une fois la normalisation terminée que nous disposerons d'implémentations auditées, de vecteurs de test et d'un support au niveau matériel. Une adoption généralisée peut réduire le risque et la difficulté d'intégration dans la couche de consensus de Bitcoin. Nous recommandons d'attendre la publication officielle de FN-DSA ; d'ici là, Falcon reste dans un état d'évolution.

Variante Falcon-WS : Cette variante assouplit les paramètres internes et s'appuie sur un échantillonnage par rejet pour compenser, compressant la taille totale à 1114 octets au niveau 1 et 2387 octets au niveau 5, réduisant encore la taille par rapport au Falcon original. Cette direction a une valeur de recherche mais ne sera pas incluse dans la norme officielle et nécessite une validation cryptanalytique supplémentaire. Les recherches existantes ont trouvé des failles dans les preuves d'infalsifiabilité forte de ses schémas dérivés (l'infalsifiabilité ordinaire n'est pas affectée).

De meilleurs schémas émergeront-ils à l'avenir ? Outre les schémas ci-dessus, la famille Fiat-Shamir remonte à BLISS en 2013. Le dernier résultat de Gärtner à CRYPTO 2025, basé sur des hypothèses matures, a des tailles de papier comparables à Falcon. La cause profonde de la difficulté d'ingénierie de cette famille réside dans la sécurité de mise en œuvre : BLISS a été cassé par des attaques par canal auxiliaire en raison d'un échantillonnage gaussien à temps non constant ; les schémas ultérieurs n'ont pas complètement résolu ce problème, et le dernier résultat suggère également que la protection de l'étape d'échantillonnage est encore plus difficile. Tant que le problème n'est pas résolu, ces schémas ne sont attrayants que sur le plan théorique et ne conviennent pas au déploiement.

Les signatures sur réseaux et celles à base de hachage peuvent se compléter. Les signatures sur réseaux peuvent servir de composants de schémas hybrides. Par exemple, dans SHRINCS, le chemin de récupération sans état utilise actuellement des signatures SPHINCS+ de plusieurs kilo-octets ; les remplacer par des signatures Falcon (ou Falcon-WS) serait plus petit et plus rapide à vérifier, réduisant considérablement le surcoût du chemin de récupération peu fréquent sans affecter le chemin d'utilisation quotidienne.

Conclusions de la recherche

Le classement des candidats sur réseaux est clair : Hawk s'est retiré de la compétition après l'attaque de l'équipe Anthropic ; Dilithium a la difficulté de mise en œuvre la plus faible et est le seul schéma avec une base de recherche pour la dérivation de clés, mais sa taille n'est pas favorable aux coûts sur la chaîne de Bitcoin ; Falcon combine une taille compacte, une vérification rapide et des hypothèses de sécurité matures ; sa principale faiblesse — l'arithmétique à virgule flottante du côté de la signature — a déjà une solution technique viable. Si nous devions choisir aujourd'hui un schéma de signature sur réseaux pour Bitcoin, nous choisirions Falcon-1024.

Pour l'instant, notre point de vue est cohérent avec le rapport sur les signatures à base de hachage : la voie conservatrice à court terme reste les signatures à base de hachage, avec les hypothèses de sécurité les plus matures et le risque le plus faible, adaptées comme schéma de transition. Une fois FN-DSA officiellement finalisé, avec des spécifications stables, des bases de code auditées et un support des portefeuilles matériels, Falcon apportera des améliorations significatives par rapport aux signatures purement à base de hachage ; un déploiement hybride peut également être adopté, permettant aux deux systèmes de signature de se compléter.