vignette|IBM Quantum System One à Ehningen en Allemagne La cryptographie post-quantique est une branche de la cryptographie visant à garantir la sécurité de l'information face à un attaquant disposant d'un ordinateur quantique. Cette discipline est distincte de la cryptographie quantique, qui vise à construire des algorithmes cryptographiques utilisant des propriétés physiques, plutôt que mathématiques, pour garantir la sécurité.
En l'effet, les algorithmes quantiques de Shor, de Grover et de étendent les capacités par rapport à un attaquant ne disposant que d'un ordinateur classique. S'il n'existe pas à l'heure actuelle de calculateur quantique représentant une menace concrète sur la sécurité des cryptosystèmes déployés, ces algorithmes permettent conceptuellement de résoudre certains problèmes calculatoires sur lesquels sont fondés plusieurs primitives populaires.
Pourquoi développer une cryptographie post-quantique De nombreux systèmes de chiffrement sont, à terme, menacés par les capacités de calcul de l'informatique quantique, domaine encore émergeant, mais où des gains progressifs dans la réduction du taux d’erreur sont constatés.
Fin , dans un livre blanc (57 pages, intitulé )https://quantumai.google/static/site-assets/downloads/cryptocurrency-whitepaper.pdf , des chercheurs de Google Quantum AI, de la fondation Ethereum, et des universités de Stanford et de Californie alertent sur le fait qu'en raison des progrès de l'informatique quantique (nouvelles techniques de correction d’erreurs et d’optimisation des algorithmes quantiques), les futurs ordinateurs quantiques pourraient casser la cryptographie à courbes elliptiques (ECC) avec beaucoup moins de ressources et donc plus tôt qu’on ne le pensait - et peut-être en quelques minutes seulement. Or, la cryptographie sur les courbes elliptiques (ECC) est encore utilisée en 2026 par la majorité des blockchains dont pour Bitcoin, Ethereum, Solana, Cardano, Polkadot.
Entre autres, le théorème de Mosca, tente de répondre à la question sur la date dès laquelle une organisation doit agir dans la mesure de proteger ses données des menaces que posent les ordinateurs quantiques.
L'algorithme de Shor appliqué au problème mathématique qui sécurise aujourd’hui la plupart des blockchains, l'ECDLP‑256. Il peut être exécuté avec moins de qubits logiques et de portes Toffoli, ou qubits logiques + de portes Toffoli. Cela correspond à moins de qubits physiques, soit environ 20 fois moins de qubits que ce que les estimations précédentes estimaient nécessaires. Et l'opération serait exécutable sur une architecture supraconductrice réaliste (un ordinateur quantique doté de à qubits logiques — soit environ qubits physiques dans une architecture supraconductrice). Dans ces conditions, d'après un modèle vérifié par Google via une preuve à divulgation nulle de connaissance, Shor briserait alors l'ECDSA ou l'EdDSA en quelques minutes. En terme de vitesse de calcul, il existe deux types d’ordinateurs quantiques : les plus rapides pourraient alors intercepter des transactions en cours. L'étude montre aussi que certaines fonctions avancées des blockchains modernes présentent des failles, et que les solutions techniques devront être accompagnées de règles publiques pour gérer, par exemple, les cryptomonnaies stockées sans avoir été utilisées, ou oubliées. Elle conclut que toutes les cryptomonnaies encore vulnérables doivent passer à une sécurité résistante aux futurs ordinateurs quantiques.
En effet, presque tous les systèmes de chiffrement et de stockage sécurisé de mots de passe (y compris dans la finance traditionnelle et dans une partie de la FinTech) sont concernés, et comme la presque totalité des blockchains repose sur l'ECC (ECDLP‑256) pour chiffrer et protéger les signatures de transactions, sécuriser les portefeuilles de cryptomonnaies et protéger les clés publiques des détenteurs de cryptomonnaies, presque toute la valeur économique du secteur des cryptomonnaies et autres cryptoactifs serait menacée par la mise au point d'un tel ordinateur.
La migration vers une cryptographie post‑quantique pourrait être couteuse et complexe, mais Google souhaite alerter sans paniquer ; encourageant une transition rapide (horizon 2029) et coordonnée vers la cryptographie post‑quantique (PQC, déjà bien étudiée et standardisée).
Ce livre blanc invite aussi à : limiter l’exposition des adresses vulnérables (ne pas réutiliser les adresses) ; prévoir des politiques pour les coins abandonnés (clés jamais dépensées) ; étudier des blockchains déjà compatibles PQC ou hybrides.
Selon les auteurs du livre blanc, ce moment est une singularité de discontinuité dans l'Histoire de la cybersécurité, qu'il faut anticiper dès que possible, pour notamment sécuriser les blockchains ().
Algorithmes quantiques et cryptographie
En 1995, Peter Shor a publié un algorithme permettant de résoudre le problème du logarithme discret et le problème de la factorisation des entiers. Cet algorithme, utilisant les spécificités d'un calculateur quantique (dont on n'avait alors pas encore construit de prototypes), produit une réponse en temps polynomial. En comparaison, les meilleurs algorithmes classiques connus pour ces problèmes ont une complexité exponentielle en général, et sous-exponentielle mais sur-polynomiale pour les corps finis. En résumé, pour ces deux problèmes, aucun algorithme classique efficace n'est connu, mais puisqu'un algorithme quantique efficace est disponible, on dit qu'ils appartiennent à la classe de complexité BQP.
En conséquence, les constructions cryptographiques dont la sécurité repose sur le problème du logarithme discret (notamment l'échange de clé de Diffie-Hellman et la signature ECDSA), ou sur le problème de la factorisation d'entiers (notamment la signature RSA) seraient vulnérables à un attaquant disposant d'un calculateur quantique suffisamment grand et fiable.
L'algorithme de Grover, quant à lui, améliore de manière faible mais générique l'efficacité des problèmes de recherche. Contrairement à l'algorithme de Shor, il ne dote pas l'attaquant d'un avantage exponentiel, mais seulement quadratique, c'est-à-dire qu'il divise le niveau de sécurité d'un problème de recherche par deux.
Cryptographie symétrique En 2018, le principal algorithme quantique affectant les cryptosystèmes symétriques est l'algorithme de Grover. Cet algorithme est générique, c'est-à-dire qu'il s'applique en principe à toute primitive indépendamment de sa construction, et permet d’effectuer une recherche parmi éléments en temps à la place de dans le cas classiques.
Par conséquent, la sécurité des algorithmes n'est affectée que par un facteur 2. Autrement dit, pour atteindre la même sécurité que dans le modèle classique, il suffit de doubler la taille des clefs utilisées, ce qui ne pose aucune difficulté conceptuelle, mais peut nécessiter des ajustement techniques. En effet, de nombreux algorithmes symétriques sont conçus et analysés avec une taille de clef fixe.
Dans certains cas, il est possible qu'une construction symétrique soit sujette à des attaques spécialisées par l'algorithme de Simon, ce qui s'est produit pour un schéma proposé à la compétition CAESAR. Enfin, l'algorithme d'Ambainis permet de gagner un facteur polynomial dans la recherche de collisions.
Cryptographie à clef publique Pour les problèmes de la factorisation d'un entier , le meilleur algorithme classique connu est en complexité temporelle heuristique
Ce qui permet d'appuyer la sécurité d'algorithmes tels que la signature de Rabin à 128 bits en utilisant un module de 3072 bits. La sécurité d’une signature RSA utilisant un tel module est alors d'au plus 128 bits face à un attaquant classique. Le meilleur algorithme quantique connu possède une complexité quadratique en ; adapter la sécurité de RSA à ce contexte serait possible, mais requiert des tailles de clef phénoménales, de l'ordre du téraoctet. En pratique, au-delà des problèmes de stockage et de transmission de telles clefs et de tels messages, l'inconvénient est que toutes les opérations sont ralenties d'autant. De plus, il n'existe pas de preuves que l'algorithme de Shor soit le plus efficace possible : chercher à sauver RSA dans ce contexte est une course perdue d'avance.
De manière générale, les algorithmes à clef publique reposant sur la factorisation peuvent être considérés cassés par un attaquant quantique : RSA, Paillier, Naccache-Stern, Rabin, Benaloh, Blum-Goldwasser, Damgård–Jurik, Goldwasser-Micali, Okamoto-Uchiyama, Schmidt-Samoa.
Le problème du logarithme discret peut aussi être résolu par une variante du même algorithme, de sorte que les algorithmes à clef publique dont la sécurité repose sur l'hypothèse de la difficulté du logarithme discret sont également cassés par l'algorithme de Shor. Contrairement au cas classique, où le crible du corps de nombres s'applique dans les corps finis mais pas en général dans le groupe des points rationnels d'une courbe elliptique, l'approche de l'algorithme de Shor ne fait aucune différence.
Ainsi, les algorithmes à clef publique reposant sur la difficulté du calcul d'un logarithme discret peuvent être considérés cassés par un attaquant quantique : Diffie-Hellman, Cramer-Shoup, DSA et ECDSA (aussi ses précurseurs Schnorr et ElGamal, et ses variantes comme EdDSA), SRP
D'autres problèmes classiquement difficiles reposant sur des problèmes d'arithmétique modulaire sont eux aussi affectés par des variantes de l'algorithme de Shor.
Candidats post-quantiques Plusieurs constructions cryptographiques ne sont pas affectées par les attaques discutées ci-dessus, et constitueraient une solution facile de substitution. Par exemple, on peut espérer construire l'équivalent de constructions à clef publique en n'utilisant que des primitives symétriques. Mais le risque demeure qu'un algorithme quantique (qui n'a pas encore été découvert) puisse les casser.
La communauté cryptographique s'est donc tournée vers des approches qu'un attaquant quantique ne peut pas casser. La logique générale est de construire des primitives cryptographiques à partir de problèmes NP-complets, dont on sait qu'un ordinateur quantique (limité à la classe BQP) ne peut les résoudre plus efficacement qu'un ordinateur classique, sous l'hypothèse que P ≠ NP. Les candidats les plus sérieux reposent sur les problèmes suivants : Problèmes de vecteurs courts dans les réseaux euclidiens (1996) ; Décodage de codes linéaires aléatoires (1978) ; Inversion de polynômes multivariés (1995) ; Navigation dans les isogénies des courbes elliptiques supersingulières (2006) ; Inversion de fonctions de hachage (1978). Le prix à payer est une perte d'efficacité et des clefs plus larges. Pour essayer de gagner sur ces terrains, plusieurs propositions ont été faites qui n'ont qu'heuristiquement la sécurité d'un problème NP. La conséquence est que parfois, ces variantes s'avèrent vulnérables à des attaques classiques (ou quantiques).
En 2017, le NIST a annoncé une compétition visant à établir une standardisation des algorithmes cryptographiques post-quantiques. Ce protocole de standardisation, a fait émerger 4 candidats pour la standardisation en : un schéma d’encapsulation de clefs, dont la sécurité repose sur la sécurité de problèmes de réseaux euclidiens (structurés), ainsi que trois schémas de signature numérique, CRYSTALS-Dilithium, et , les deux premiers reposant sur des hypothèses de sécurité sur les réseaux euclidiens (structurés) et le dernier étant une construction fondée sur les fonctions de hachage.
Remarque : les noms de code de la compétition étaient Kyber et Dilithium, mais depuis la ratification finale par le NIST en , les noms officiels sont devenus ML-KEM (pour Kyber) et ML-DSA (pour Dilithium).
Réseaux euclidiens
vignette|alt=Réduction de réseaux|Réseau euclidien engendré par v₁ et v₂ et une base réduite u₁ et u₂