How Bitcoin Survives Quantum Computers (ft. Dan Boneh)

Dan Benet, cryptographe légendaire et professeur à Stanford, a présenté une conférence sur les signatures post-quantiques pour les blockchains, un sujet d'actualité en raison des menaces quantiques imminentes pour l'écosystème blockchain, comme la fin potentielle de Bitcoin. La communauté crypto développe activement des signatures post-quantiques, notamment basées sur les réseaux (lattices), les fonctions de hachage (hash-based), les isogénies et les preuves à connaissance nulle (ZK proofs). Bien que Benet ait longtemps préconisé les signatures basées sur les réseaux pour leur structure algébrique, il estime que le monde s'oriente vers les signatures basées sur les fonctions de hachage, surtout pour Bitcoin et Ethereum. La raison principale est que ces dernières n'introduisent pas de nouvelles hypothèses, ne s'appuyant que sur SHA-256 pour Bitcoin, ce qui est très apprécié par les développeurs de Bitcoin Core. Les signatures basées sur les réseaux sont perçues avec méfiance en raison de la peur des hypothèses, illustrée par l'incident "Hawk". La première partie de la conférence était un cours intensif sur les signatures basées sur les fonctions de hachage. Benet a introduit trois concepts clés : 1. **Signatures à usage unique (One-Time Signatures - OTS)** : Sécurisées tant qu'une seule signature est émise par clé publique. Si deux messages sont signés avec la même clé publique, la sécurité est compromise. Elles produisent des signatures courtes, mais la vérification peut être lente. 2. **Signatures à usage limité (Few-Time Signatures - FTS)** : Sécurisées tant qu'un petit nombre de messages est signé avec une même clé privée. La sécurité se dégrade avec l'augmentation du nombre de signatures. 3. **Signatures à usage limité avec état (Stateful Few-Time Signatures)** : Elles combinent plusieurs OTS dans un arbre de Merkle. Chaque feuille de l'arbre permet de signer un message. Elles offrent des signatures très courtes et une vérification rapide. Cependant, le signataire doit maintenir un état (un compteur) pour s'assurer que chaque clé publique n'est utilisée qu'une seule fois. Ne pas mettre à jour cet état ou le désynchroniser sur plusieurs appareils peut compromettre le schéma de signature. Benet insiste sur l'utilisation de schémas de signature hybrides (combinés avec ECDSA) pour les signatures avec état, afin de garantir la sécurité jusqu'à l'avènement de l'informatique quantique ("Qday"). Les clés publiques et privées dans ces systèmes sont très courtes. La clé privée est générée à partir d'une graine (seed) à l'aide d'une fonction pseudo-aléatoire (PRF). Les clés secrètes pour les feuilles de l'arbre sont générées à la volée. La norme NIST, SLHDSA, est basée sur le framework SPHINCS+. Elle est conçue pour 2^64 signatures sans état, ce qui signifie qu'aucun état n'est nécessaire. Les signatures sont grandes (8 kilooctets), mais la clé publique est toujours courte. La vérification consiste à redériver la clé publique à partir de la signature et à la comparer à la clé publique enregistrée. Bien adaptée aux systèmes de mise à jour logicielle où la taille de la signature est moins critique, elle est mal adaptée aux blockchains en raison de la taille des transactions. Le NIST a donc proposé une version réduite de SPHINCS, supportant 2^24 signatures avec des signatures plus courtes (3,8 kilooctets). Le temps de signature est élevé (environ un milliard de hachages), mais la vérification est très rapide (300 hachages), ce qui est avantageux pour les ZK-snarks. Le fonctionnement de SPHINCS/SLHDSA repose sur la construction d'un "arbre virtuel" (XMSS tree) de clés publiques de signatures à usage unique. La clé secrète est une clé de PRF qui génère toutes les clés secrètes. Chaque feuille de l'arbre signe la racine d'un autre arbre de clés, et ainsi de suite, jusqu'à atteindre un grand nombre de feuilles (par exemple, 2^64). Cet arbre n'est jamais matérialisé entièrement ; seule la partie nécessaire à la signature d'un message est générée à la volée. Les feuilles de l'arbre virtuel signent des clés publiques de FTS sans état. La signature d'un message implique le choix aléatoire d'une feuille, la dérivation de ses clés, la signature du message avec le FTS, puis la signature de la clé publique du FTS avec l'OTS de la feuille, et enfin l'inclusion du chemin d'authentification dans l'arbre. La sécurité est assurée en limitant le nombre de fois qu'une feuille est utilisée, grâce à un processus aléatoire qui garantit une probabilité de falsification inférieure à 2^-128. L'utilisation de la sélection aléatoire des feuilles est cruciale pour maintenir le caractère sans état du schéma. Si les feuilles étaient utilisées séquentiellement (de gauche à droite), un état serait nécessaire. Benet a ensuite abordé l'intégration de ces signatures dans Ethereum (projet Leanig) et Bitcoin (projet Shrinks). L'idée est de générer deux types de clés : 1. **Une clé à long terme sans état** : Une version réduite de SLHDSA supportant, par exemple, un million de signatures. Dérivée d'une phrase de départ (seed phrase). 2. **Une clé à court terme avec état** : Conçue pour signer une seule transaction et changée à chaque transaction. Elle est générée à partir d'une phrase de départ, d'un identifiant de portefeuille et, surtout, d'un compteur avec état. La clé à court terme est utilisée pour les transactions normales, fournissant des signatures courtes. La clé à long terme sert à la récupération en cas de perte de l'état (identifiant de portefeuille ou compteur) de la clé à court terme. Si l'état est compromis, l'utilisateur peut réinitialiser la chaîne de clés à court terme en utilisant la clé à long terme. L'utilisation d'une FTS pour la clé à court terme (supportant 5 à 10 signatures au lieu d'une seule) est une mesure de sécurité supplémentaire pour éviter la compromission en cas de réutilisation accidentelle de l'état. Benet a réitéré l'importance d'utiliser des schémas hybrides pour les signatures avec état. Les portefeuilles matériels (hardware wallets) sont réticents aux signatures avec état en raison de la complexité d'ingénierie et de la gestion de la mémoire non-volatile limitée. Ils devraient décharger l'état sur un ordinateur, mais cela introduit des défis de confiance. Les entreprises de portefeuilles s'opposent également aux signatures basées sur les hachages en raison de leur lenteur actuelle sur les processeurs existants, bien que cela devrait être résolu avec l'accélération matérielle future. La transition vers les signatures basées sur les hachages implique des compromis. Par exemple, la dérivation de clés renforcée (hardened key derivation) dans les portefeuilles HD, qui utilise l'algèbre des clés publiques ECDSA et Schnorr, n'est pas possible avec les signatures basées sur les hachages. Benet a ensuite présenté des travaux sur les **signatures de seuil basées sur les hachages**. Les solutions génériques comme le multisignature entraînent de grandes signatures et révèlent publiquement le seuil. Les preuves ZK (snarks) pour agréger les signatures ne sont pas acceptables pour Bitcoin. Les solutions basées sur le chiffrement homomorphe complet (FHE) ou le calcul multipartite sécurisé (MPC) sont trop lentes actuellement. L'approche proposée par Benet et son équipe (projet Shrimps) est une solution hybride : la signature finale est entièrement basée sur les hachages (vérifiable par la blockchain), mais le mécanisme de seuil est basé sur les réseaux (lattices). Cela signifie que la décision de seuil est une affaire privée du détenteur de la clé, et la blockchain n'a pas connaissance des réseaux. Si les hypothèses des réseaux sont compromises, la clé privée est perdue. La défi majeur pour les signatures de seuil à usage unique est la coordination. Si les signataires ne coordonnent pas, un attaquant peut obtenir des signatures sur différents messages en collectant des parts de signature auprès de différents sous-ensembles de signataires, compromettant la clé. La solution est d'utiliser une propriété d'intersection de quorum, où le seuil doit être supérieur à (n+f)/2 (n étant le nombre total de signataires, f le nombre de signataires malhonnêtes). Cela garantit qu'il est impossible d'obtenir suffisamment de parts pour signer deux messages différents. Pour les signatures à usage limité (D-time signatures), la généralisation de l'intersection de quorum implique qu'un schéma FTS sécurisé pour 2D signatures est nécessaire pour obtenir une signature de seuil D-time sans coordination. La construction des signatures de seuil basées sur les hachages repose sur une nouvelle notion : la **PRF de seuil sensible au contexte (Context-Aware Threshold PRF - CATPRF)**. Une PRF de seuil traditionnelle permet de reconstruire la valeur de la PRF si suffisamment de parts d'évaluation sont combinées. Une CATPRF renforce cette propriété : un attaquant n'apprend rien sur la valeur de la PRF à moins d'avoir T parts d'évaluation pour X, *toutes sous le même contexte*. Le contexte, dans ce cas, est le message signé. Benet a illustré la construction de signatures de seuil à usage unique (Winter's OTS), également appelées "WATTS". 1. Un générateur de clés crée une CATPRF (basée sur les réseaux pour de grands N et T) et distribue les clés secrètes de la PRF aux signataires. 2. La PRF est utilisée pour générer la ligne inférieure d'une table de hachage de Winter. 3. Le générateur de clés chiffre chaque élément de la table de Winter avec un masque à usage unique (one-time pad) dérivé de la PRF, créant une "table de Winter chiffrée" qui est donnée au combinateur (un tiers non fiable). 4. Lors de la signature d'un message, chaque signataire révèle une part d'évaluation de la PRF pour chaque bloc de la table de Winter, utilisant le message comme contexte. 5. Si le combinateur reçoit suffisamment de parts, il peut reconstruire la valeur de la PRF, démasquer les éléments correspondants dans la table de Winter chiffrée et reconstruire la signature. L'utilisation du message comme contexte est essentielle pour la sécurité. Sans cela, un attaquant pourrait combiner des parts provenant de la signature de différents messages pour forger une signature. La sécurité de WATTS est prouvée sous des hypothèses spécifiques sur la CATPRF, la fonction de hachage et la propriété "cover-free" de la fonction P qui mappe les messages. Cette approche peut être étendue aux FTS (XMSS, SPHINCS). Cependant, elle ne s'applique pas directement à SLHDSA en raison de la taille énorme de l'arbre virtuel (2^64 feuilles), ce qui rendrait la clé publique du combinateur trop grande. Pour SLHDSA, des techniques MPC seraient nécessaires, mais cette méthode simplifierait grandement le processus MPC en réduisant le nombre d'opérations de hachage. Les défis futurs incluent le développement d'un générateur de clés distribué (DKG) pour ces signatures basées sur les hachages et la possibilité de modifier N et T à la volée (silent setup). En conclusion, les signatures basées sur les hachages sont l'avenir des blockchains post-quantiques. L'approche hybride (mécanisme de seuil basé sur les réseaux, signature finale basée sur les hachages) offre une solution aux problèmes de seuil. La taille des signatures reste un défi, mais des solutions comme la "snarkification" pour Ethereum et l'augmentation de la taille des blocs pour Bitcoin sont envisagées. La question des actifs abandonnés après l'avènement des ordinateurs