Vers une cryptographie post-quantique
Vous êtes ici
Read in English [2]Vers une cryptographie post-quantique
En quoi les technologies quantiques menacent-elles la cryptographie ?
Adeline Roux-Langlois1 La cryptographie repose sur des problèmes mathématiques choisis parce qu’ils sont extrêmement difficiles à résoudre et à contourner avec des ordinateurs classiques. Les futures machines quantiques devraient cependant y parvenir bien plus facilement, rendant obsolètes nos systèmes de protection. Pour l’instant, les ordinateurs quantiques ne sont pas encore assez puissants et développés pour vaincre les protocoles cryptographiques actuels, mais il faut s’y préparer.
Le National institute of standards and technology (Nist)2, chargé d’établir différents standards technologiques et métrologiques aux États-Unis, a ainsi lancé dès 2017 une compétition internationale afin d’atteindre un consensus scientifique autour de la cryptographie post-quantique. Un processus qui est entré dans sa troisième et dernière phase, avec aussi bien des équipes de chercheurs académiques que des industriels. Parmi les soixante-neuf soumissions initiales, le Nist choisit à chaque étape celles qui restent en compétition en se reposant sur des critères comme la sécurité, les performances et les caractéristiques de l’implémentation. Il prend également en compte les études publiées par la communauté scientifique et les éventuelles attaques faites contre les schémas.
Sur quoi repose actuellement la cryptographie ?
A. R.-L. Il y a deux approches pour chiffrer des données, le chiffrement à clé privée et celui à clé publique. Dans le chiffrement à clé privée, les usagers se partagent une clé. Cette approche est plus sécurisée, moins menacée par les technologies quantiques, mais elle est également moins pratique à utiliser dans de nombreux cas de figure. Le système de chiffrement à clé publique repose quant à lui sur deux clés : une qui est gardée secrète et l’autre qui est disponible à n’importe qui. Par exemple, tout le monde peut envoyer des mails chiffrés à un destinataire qui sera le seul à pouvoir les lire. Il faut néanmoins avoir confiance dans la difficulté du problème à partir duquel les clés sont calculées, car tout algorithme capable de le résoudre en un temps raisonnable donnera accès aux données que l’on voulait protéger. Garantir la difficulté des problèmes forme le socle de toutes les constructions de sécurité.
On retrouve actuellement deux grands types de problèmes difficiles : la factorisation et le logarithme discret. La factorisation consiste à décomposer un nombre en un produit de deux nombres premiers, ce qui est bien plus difficile qu’il n’y paraît dès que l’on manipule de très grands nombres. De même, aucun algorithme ne parvient pour l’instant à calculer efficacement un logarithme discret. Le concours du Nist ne se limite cependant pas qu’à la question du chiffrement. D’autres algorithmes devront travailler sur la signature, c’est-à-dire authentifier l’origine d’un message sans que ce soit falsifiable. Dans les deux cas, les critères concernent bien entendu la sécurité, mais aussi la rapidité ou la fluidité du système.
Quelles approches sont proposées pour une cryptographie post-quantique ?
A. R.-L. Plusieurs types de solutions sont privilégiées. L’une d’elles, la cryptographie sur réseaux euclidiens, consiste à trouver les plus courts vecteurs entre deux points sur une grille dans un espace à plusieurs centaines de dimensions. Chaque vecteur a ainsi énormément de coordonnées et le problème devient extrêmement difficile à élucider. Autre solution, la cryptographie multivariée repose sur un principe un peu similaire, en proposant de résoudre des polynômes avec tellement de variables que le calcul n’est plus possible dans un temps raisonnable. Une autre approche encore utilise les codes correcteurs d’erreurs, qui servent à l’origine à améliorer les communications bruitées, par exemple pour rendre son apparence à une vidéo gravée sur un DVD qui se serait dégradé. Certains de ces codes fournissent un cadre très efficace pour le chiffrement, mais fonctionnent assez mal quand il s’agit de garantir une signature.
La construction de réseaux euclidiens est particulièrement présente chez les finalistes, car elle marche aussi bien sur le chiffrement que les signatures. Mais toute la communauté n’est pas d’accord pour se focaliser autant dessus. Le Nist préfère en effet multiplier les approches pour établir ses standards. Si jamais une solution est attaquée, les autres restent garanties. On retrouve par exemple l’algorithme SPHINCS+, issu de l’université d’Eindhoven aux Pays-Bas, qui repose sur des fonctions de hachages. Une empreinte numérique est attribuée aux données, tandis qu’il est extrêmement difficile de réaliser l’opération inverse, même avec un algorithme quantique. Les signatures ainsi obtenues sont cependant coûteuses en ressources.
Quelles sont les contributions françaises encore en lice dans ce concours ?
A. R.-L. On compte sept algorithmes impliquant des chercheurs en poste en France. Sur la question du chiffrement, Crystals-Kyber, NTRU et Saber reposent sur les réseaux euclidiens, tandis que Classic McEliece est basé sur les codes correcteurs d’erreur. Damien Stehlé, professeur à l’ENS Lyon et membre du Laboratoire de l’informatique du parallélisme3, ainsi que Nicolas Sendrier, du centre de recherche Inria de Paris, y participent.
Dans la catégorie signature, les algorithmes Crystals-Dilithium et Falcon utilisent les réseaux euclidiens, et Rainbow préfère les systèmes multivariés. On retrouve là encore Damien Stehlé, mais aussi Pierre-Alain Fouque, professeur à Rennes 1 et membre du laboratoire Irisa, et Jacques Patarin, professeur à l’université de Versailles-Saint-Quentin-en-Yvelines.
Et vous-même, quels sont vos travaux sur ces questions ?
A. R.-L. J’étudie surtout sur la cryptographie à base de réseaux euclidiens, où j’apporte des preuves théoriques que la sécurité des constructions cryptographiques repose sur des problèmes suffisamment difficiles pour qu’on lui fasse confiance. Le chiffrement et la signature sont les premières applications auxquelles on pense, mais cela peut également s'appliquer à la confidentialité très particulière du vote électronique. Il faut en effet s’assurer de l’authenticité des votes avant de les compter, mais sans dévoiler qui a voté pour quoi. Je travaille également sur l’authentification anonyme, qui permet notamment de prouver que l’on appartient à un groupe sans dévoiler d’autres informations, ou de prouver qu’on est majeur sans donner son âge ou sa date de naissance. ♦
- 1. Chargée de recherche CNRS à l’Institut de recherche en informatique et systèmes aléatoires (Irisa – unité CNRS/Université Rennes 1/ENS Rennes/INSA Rennes/Université Bretagne-Sud/INRIA/IMT Atlantique).
- 2. Institut national des normes et de la technologie.
- 3. LIP (CNRS/ENS Lyon/Université Claude-Bernard).
Voir aussi
