On connait les premiers algorithmes de cryptographie post-quantique

Pour savoir qui a le droit de déchiffrer ou signer un message, la cryptographie à clé publique repose sur des problèmes mathématiques difficiles et n’autorise ces opérations qu’à ceux qui en détiennent la solution. En même temps, tout le monde doit pouvoir chiffrer un message ou vérifier une signature d’un utilisateur donné. Ces processus, généralement invisibles et automatiques, ont par exemple lieu à chaque échange de mails. Les intrus, qui n’ont pas la bonne réponse en leur possession, ne doivent pas pouvoir réaliser l’opération inverse et ainsi calculer la solution qu’ils n’ont pas. La cryptographie a donc choisi une série de problèmes spécifiquement parce qu’ils sont simples à résoudre dans un sens, mais impossibles dans l’autre dans un temps raisonnable, même avec les ordinateurs les plus puissants.

L’essor annoncé des ordinateurs quantiques a cependant changé la donne. Ces derniers ne seront pas simplement des versions améliorées de nos ordinateurs de bureau : fonctionnant avec des principes physiques complètement différents, et au-delà de la seule question de leur puissance, ils pourront résoudre bien plus facilement certains problèmes, dont ceux utilisés par la cryptographie actuelle. Si pour l’instant les premiers démonstrateurs d’ordinateurs quantiques sont encore loin de pouvoir réaliser ce genre de tâches, pas question d’attendre qu’ils le soient pour se prémunir d’un tel risque.

C’est pourquoi le National Institute of Standards and Technology (NIST) – l’agence américaine chargée des normes technologiques - a lancé en 2016 un appel international à contributions pour définir des standards de sécurité adaptés aux futurs développements de l’informatique : la cryptographie post-quantique.

« Le NIST a lancé cet appel sur la demande de la NSA, précise Pierre-Alain Fouque, professeur à l’Université de Rennes 1 et chercheur au sein de l'Institut de recherche en informatique et systèmes aléatoires (IRISA, CNRS/Université de Rennes 1). Les militaires considèrent en effet des durées de vie particulièrement longues pour la sécurité : il faut vingt ou trente ans pour concevoir et construire un sous-marin, qui va fonctionner pendant plusieurs décennies et dont les communications doivent rester indéchiffrables encore vingt ans après son retrait du service. Or, il est raisonnable de penser que de vrais ordinateurs quantiques pourraient émerger avant que tout le matériel militaire actuel ne soit complètement hors d’usage. »

Le concours s’est déroulé en plusieurs étapes. Quatre-vingt-deux projets ont initialement été soumis, répartis entre deux approches. On retrouve d’abord les schémas de chiffrement à clé publique, qui permettent par exemple à tout le monde d’envoyer un message chiffré à une personne qui sera la seule à pouvoir les lire, puis la génération de signatures électroniques, qui authentifient un acte ou un document. Le NIST a annoncé, le 5 juillet, les résultats du troisième round, où l’on retrouve quatre candidats et huit projets alternatifs. Parmi les algorithmes retenus, CRYSTALS-KYBER est le seul à traiter du chiffrement à clé publique, tandis que CRYSTALS-DILITHIUM, SPHINCS+ et FALCON, auquel participe Pierre-Alain Fouque, sont dédiés à la génération de signatures électroniques.