Cryptographie post-quantique : forte présence d’Inria au NIST

L'ordinateur quantique, enjeu majeur de la cryptographie

La construction d'un ordinateur quantique qui pourrait effectuer certains calculs hors de portée des ordinateurs classiques est une avancée majeure envisagée depuis de nombreuses décennies. Cette perspective est toutefois devenue plus tangible, comme en témoignent les avancées récentes soutenues par des investissements privés et publics de grande ampleur, telle l'initiative européenne "Quantum Flagship" . La construction d'un tel ordinateur engendrerait un cataclysme dans le monde de la cryptographie.

En effet, parmi les algorithmes cryptographiques qui sécurisent actuellement nos communications, la plupart de ceux qui permettent d'échanger une clé secrète entre deux protagonistes afin d'initier une communication sécurisée, et l'immense majorité des procédés de signature numérique, ont une sécurité qui repose sur la difficulté de résoudre certains problèmes comme la factorisation de grands entiers. Or, ces problèmes pourraient être résolus beaucoup plus facilement avec un ordinateur quantique, et augmenter la taille des nombres manipulés influerait peu sur la difficulté.

La construction d'un ordinateur quantique imposerait donc de remplacer de nombreux algorithmes cryptographiques à clé publique, comme le RSA et le protocole de Diffie-Hellman, par des systèmes fondés sur d'autres types de problèmes difficiles. Ces systèmes alternatifs doivent être définis dès à présent car il est indispensable d'en éprouver la sécurité avant d’en généraliser l’usage, ce qui prend plusieurs années. Par ailleurs, certaines données sensibles doivent rester protégées pendant plusieurs décennies, ce qui semble être un horizon envisageable pour la réalisation d'un ordinateur quantique.

Sept projets Inria finalistes au NIST

C'est pourquoi l'organisme de standardisation américain NIST (National Institute of Standards and Technology)  a lancé un effort international pour la standardisation d'algorithmes cryptographiques dits postquantiques, ce qui signifie qu'ils résisteraient également aux adversaires disposant d'un ordinateur quantique. Ce processus de standardisation se déroule sous la forme d'une compétition internationale à laquelle tous les volontaires étaient invités à soumettre, en novembre 2017, de nouveaux algorithmes d'échange de clé et de nouveaux schémas de signature. Le NIST a alors reçu 69 candidats valides, parmi lesquels 12 ont été proposés par des chercheurs d'une équipe-projet Inria. Ces candidats ont depuis été rendus publics et leur sécurité fait actuellement l'objet d'une analyse très précise menée par l'ensemble de la communauté cryptographique. Sur la base des premières évaluations, le NIST a sélectionné en janvier dernier 26 soumissions pour la suite de la compétition, dont plus du quart émane d'équipes-projets Inria.

Sept propositions dans lesquelles Inria est impliqué sont l'aboutissement de nombreux travaux de recherche menés par les équipes-projets ARIC, SECRET, POLSYS et GRACE, sur la possibilité de fonder des systèmes cryptographiques sur des problèmes alternatifs à ceux utilisés usuellement. Après plusieurs années d'analyse, cet effort de standardisation devrait aboutir vers 2022.

Les sept algorithmes candidats proposés par Inria reposent sur divers types de problèmes algorithmiques dont la résolution est difficile. Ils se répartissent de la manière suivante :

• Algorithmes candidats fondés sur des problèmes issus de la théorie des codes : BIKE, Classic McEliece, ROLLO (impliquant tous des membres de l’équipe-projet SECRET)
• Algorithmes candidats fondés sur des problèmes liés aux réseaux euclidiens : CRYSTALS-DILITHIUM, CRYSTALS-KYBER (impliquant tous des membres de l’équipe-projet ARIC)
• Algorithme candidat utilisant les isogénies d’une courbe elliptique : SIKE (impliquant des membres de l’équipe-projet GRACE)
• Algorithme candidat fondé sur la résolution de systèmes polynomiaux multivariés : GeMSS (impliquant des membres de l’équipe-projet POLSYS).