Ces dernières années, les universités, l'industrie et le gouvernement ont investi de l'énergie et des ressources dans le domaine de l'informatique quantique, dans des ordinateurs qui exploitent les phénomènes de la mécanique quantique pour résoudre des problèmes mathématiques difficiles ou peu pratiques pour les ordinateurs conventionnels.
Si la production à grande échelle d'ordinateurs quantiques commence un jour, ils seront en mesure de détruire de nombreux systèmes cryptographiques à clé publique (ou asymétriques) actuellement utilisés. Cela porterait gravement atteinte à la confidentialité et à l'intégrité des communications numériques sur Internet et ailleurs.
Dans ce contexte, l'objectif de la cryptographie post-quantique (o sans danger quantique) consiste à développer des chiffrements sûrs, à la fois contre les attaques de cryptanalyse menées avec des ordinateurs quantiques et classiques, et pouvant interagir en même temps avec les protocoles et réseaux de communication existants.
Alors que la cryptographie à clé publique, la cryptographie à double clé pour le cryptage / décryptage, peut être sérieusement mise en danger par l'avènement des ordinateurs quantiques, la cryptographie symétrique (ou privée) et les fonctions de hachage reposent sur des problèmes résistants à algorithmes quantiques. Parmi ceux-ci, la plus grande menace pour les chiffrements symétriques est représentée parL'algorithme de Grover (conçu par Lov Grover en 1996 à i Bell Labs1). Cet algorithme fonctionnant sur un ordinateur quantique permet de rechercher un élément dans une liste non ordonnée de longueur N, dans un temps proportionnel à la racine carrée de N. Au contraire, sur un ordinateur classique, le temps serait proportionnel à N Cela signifie que pour obtenir le même niveau de sécurité, la longueur de la clé doit être doublée.
Parmi les algorithmes clés symétriques, leAdvanced Encryption Standard (AES), le Blowfish, le Deux fois ou serpent, avec une longueur de clé supérieure ou égale à 256 bits et dans des conditions appropriées, ils peuvent faire leurs preuves sans danger quantique.
Sur le front de la cryptographie asymétrique, cependant, la perspective est moins rassurante. Les cryptosystèmes à clé publique sont principalement utilisés pour effectuer deux tâches fondamentales, l'échange sécurisé de clés, pour leur utilisation ultérieure avec des chiffrements symétriques, et la signature numérique.
Les chiffrements à clé publique les plus connus et actuellement utilisés incluent:
- RSA, basé sur le problème de la factorisation des nombres entiers;
- la cryptographie à courbe elliptique, qui fonde sa sécurité sur la difficulté d'effectuer certaines opérations sur les points de ce type de courbe;
- Diffie-Hellman, s'est concentré sur la difficulté de calculer le logarithme discret sur certains groupes cycliques.
Pour chacun d'eux, il est possible de mener facilement une attaque de cryptanalyse, décrypter les informations sans utiliser la clé, au moyen duAlgorithme de Shor (conçu par Peter Shor en 19942) s'exécutant sur un ordinateur quantique. La raison pour laquelle l'algorithme de Shor est capable de «casser» les systèmes cryptographiques à clé publique est la conséquence du fait qu'ils sont basés sur des problèmes de complexité de calcul non polynomiale, qui peuvent être résolus par un ordinateur quantique en temps polynomial. Plus précisément, étant donné un entier N, l'algorithme de Shor le factorise en un temps polynomial en journal (N), tandis que sur un ordinateur classique, le temps est exponentiel en N.
Motivé par ces considérations, l'Américain Institut National des Standards et de la technologie (NIST) a entrepris la sélection d'algorithmes cryptographiques à clé publique sans danger quantique à l'issue d'un appel public, annoncé lors de la conférence PQCrypto 2016 et lancé en décembre de la même année.
L'invitation a rassemblé 82 algorithmes candidats qui, grâce à des processus d'examen par les pairs et des cycles de sélection, les ont réduits, à terminer, vraisemblablement d'ici 2024, avec la publication d'une norme.
Les nouveaux chiffrements seront adoptés par les États-Unis par analogie avec les initiatives précédentes pour l'introduction Norme de cryptage des données (DES) et AES.
Entre classes d'algorithmes post-quantique qui s'avèrent les plus prometteurs sont les algorithmes basés sur la "cryptographie basée sur le code" qui, introduite en 1978 par l'américain Robert McEliece3 pour la cryptographie à clé publique, ils n'ont pas eu beaucoup de chance en raison de la taille excessive de la clé. De même, il existe aujourd'hui des variantes capables d'offrir des tailles de clés considérablement réduites et compétitives. Ces algorithmes sont basés sur la difficulté de rechercher dans un vaste ensemble de nombres non ordonnés. Il a également été prouvé théoriquement qu'ils appartiennent à la classe des problèmes dits NP (polynômes non déterministes) qui pourraient résister au calcul quantique.
Une seconde classe, Cryptographie multivariée4, est basé sur la difficulté de résoudre des systèmes d'équations algébriques quadratiques dans de nombreuses variables (NP-dureté).
Une troisième classe est celle basée sur le concept algébrique de "treillis" (Cryptographie au latex), y compris des variantes basées sur le problème de "l'apprentissage avec des erreurs", qui consiste en la reconstruction d'une fonction à partir de certaines de ses évaluations inexactes5. Cette formulation a permis de définir des algorithmes innovants de cryptographie asymétrique, accompagnés de démonstrations de sécurité sévères.
L'implémentation de nouveaux chiffrements à clé publique sans danger quantique représente aujourd'hui un effort inévitable. L'omniprésence de l'utilisation des algorithmes à clé publique actuels affecte la vie quotidienne de chacun, de la navigation sécurisée sur Internet aux systèmes de sécurité bancaire, des signatures numériques aux crypto-monnaies.
Une course contre la montre pour certains, alors que pour d'autres, il faudra encore du temps pour que la puissance de calcul d'un ordinateur quantique atteigne le niveau nécessaire pour rendre les normes actuelles obsolètes.
Dans l'intervalle, cependant, dans le secteur privé, des géants tels que Google et IBM mènent des expériences visant à acquérir la soi-disant «suprématie quantique», se défiant mutuellement dans la réalisation de nouveaux records informatiques de plus en plus ambitieux. Par ailleurs, dans le même but, dans la sphère internationale, des superpuissances comme les États-Unis et la Chine, ainsi que l'Union européenne, investissent de plus en plus pour le développement de plans de recherche dans le domaine de l'informatique quantique. La Chine, par exemple, a récemment annoncé son intention de construire un laboratoire national des sciences de l'information quantique à Hefei d'ici 2020, qui se verra attribuer un budget pluriannuel de dix milliards de dollars.6.
Dans le même temps, dans le contexte européen, la nouvelle présidente de la Commission européenne, Ursula von der Leyen, s'est prononcée sur la question en déclarant que la l'informatique quantique c'est l'une des priorités de l'Union et elle exprime sa volonté de soutenir les initiatives de développement dans ce domaine, en mettant également les ressources informatiques européennes à la disposition des universités et de la recherche, à travers le nuage. À cette fin, l'Union a mis à disposition un milliard de dollars à utiliser dans les dix prochaines années7, pour le développement de certains projets déjà identifiés.
Dans ce contexte, la raison de la «race» spasmodique des acteurs étatiques et privés, visant à atteindre la suprématie précitée dans le domaine de la l'informatique quantique, se trouve dans les mots que Mike McCaul8, Homme politique nord-américain et membre de l'American Enterprise Institute, s'est prononcé en 2018 sur la concurrence dans le domaine de l'informatique quantique des États-Unis avec des opposants mondiaux tels que la Chine, la Russie, la Corée du Nord et l'Iran: "Je crois que toute superpuissance atteignant cette étape avant les autres aurait la première bombe nucléaire numérique".
1 Grover, "Un algorithme de mécanique quantique rapide pour la recherche de bases de données", Actes, 28e Symposium annuel de l'ACM sur la théorie de l'informatique, p. 212, 1996.
2 Shor, "Algorithms for quantum computation: Discrete log and factoring", dans Actes du 35e Symposium annuel sur les fondations de l'informatique, Santa Fe, IEEE Computer Society Press, pp. 124-134, 1994.
3 McEliece, "Système à clé publique basé sur la théorie du codage algébrique", DSN Progress Report 44, pp. 114-116, 1978.
4 Matsumoto, Imai, "Une classe de cryptosystèmes asymétriques basés sur des polynômes sur des anneaux finis", IEEE International Symposium on Information Theory, Résumé des articles, pp. 131-132, 1983.
5 Goldreich, Goldwasser, Halevi, "Cryptosystème à clé publique du problème des réductions de réseau", dans Proc. Of Crypto '97, volume 1294 de LNCS pp. 112-131, IACR, Springer-Verlag, 1997.
6https://itbrief.com.au/story/apac-jumps-on-quantum-computing-bandwagon
7https://www.ilsole24ore.com/art/la-cina-l-occidente-e-sfida-globale-big-...
8https://fedmanager.com/news/congressman-quantum-computing-equivalent-to-...
Photo: IBM
