Résumé
Sans la cryptographie, n’importe qui pourrait espionner vos conversations en ligne ou avoir accès à vos comptes bancaires. Pour se prémunir contre ces risques, votre navigateur Web et votre téléphone portable effectuent systématiquement des calculs mathématiques sur de très grands nombres, sur lesquels s’appuie la sécurité de la cryptographie utilisée au quotidien. Bien que celle-ci soit établie depuis 50 ans, Planck, de Broglie et Einstein ont mis en lumière un phénomène qui pourrait changer la donne d’ici 10 ans : la physique quantique. En effet, l’existence d’un ordinateur quantique, basé sur les principes de superposition et d’intrication quantiques, bouleverserait considérablement les normes actuelles en matière de cryptographie. Des solutions cryptographiques existent depuis longtemps pour contrer cette menace, s’appuyant sur des outils mathématiques différents : la cryptographie post-quantique. Cependant, il est essentiel d’approfondir les recherches pour obtenir des outils cryptographiques concrets pouvant être déployés dans nos produits et services d’ici 2030. C’était l’objectif principal de PROMETHEUS.
Lancé en 2018, ce projet H2020 a étudié la chaîne de la cryptographie post-quantique dans son intégralité : les bases mathématiques, les primitives de chiffrement et de signature utilisées chaque jour, et les applications qui protègent la vie privée des individus. PROMETHEUS a publié plus de cent articles, a initié 3 des 4 futurs standards en matière de cryptographie, a fourni une quinzaine de librairies publiques afin d’aider le secteur à mieux se préparer pour la transition quantique, et a validé dans un environnement significatif 4 prototypes sécurisés dans un monde quantique.
Le ministère de l’Enseignement supérieur, de la recherche et de l’innovation a discerné à PROMETHEUS le prix spécial du trophée des Étoiles de l’Europe en récompense pour son travail sur la transition vers une ère post-quantique.
Points clés à retenir
Les ordinateurs quantiques ne sont pas pour tout de suite, mais l’existence d’un tel système est sans doute la plus grande menace que la cryptographie ait jamais connue. Nous devons être prêts, car ils pourraient vite être déployés. Il est donc important de concevoir des systèmes alternatifs à la cryptographie historique que nous utilisons au quotidien. C’est notre motivation principale depuis le début du projet PROMETHEUS.
Grâce aux résultats de nos recherches, de nos travaux en normalisation, de nos implémentations et de nos prototypages de cas d’utilisation, nous avons offert à la communauté TIC un grand nombre d’améliorations en matière de cryptographie à base de réseaux euclidiens, allant des fondations aux protocoles avancés. Nous avons évalué de manière approfondie le niveau exact de maturité de cette famille de cryptographie post-quantique. Nous avons également partagé en grande partie nos découvertes (publications, librairies, prototypes de cas d’utilisation) avec des universités, avec des industriels du secteur, mais aussi avec les autorités européennes, afin de tous les préparer pour une transition réelle et en toute sécurité vers la cryptographie à résistance quantique. Trois des quatre futures normes NIST en matière de cryptographie post-quantique ont notamment été élaborées par les membres du consortium PROMETHEUS. Nous avons également fourni les premiers systèmes résistants à la menace quantique pour quatre cas d’utilisation : le vote électronique, le paiement électronique respectueux de la vie privée, l’authentification sécurisée et les renseignements sur les cybermenaces.
En récompense pour tous ces accomplissements, le ministère de l’Enseignement supérieur, de la recherche et de l’innovation a récemment discerné à PROMETHEUS le Prix spécial du trophée des Étoiles de l’Europe.
Introduction
La cryptographie protège la vie numérique des citoyens depuis des décennies et sécurise leurs communications sensibles, telles que la navigation Web, les paiements en ligne et sans contact ou les services à la maison. La plus grande réussite de ce domaine repose probablement dans le fait que les algorithmes de cryptographie, bien qu’omniprésents, passent inaperçus aux yeux des utilisateurs. Par ailleurs, les normes de cryptographie utilisées dans ces différents contextes sont parfaitement maîtrisées depuis les années 1970. Elles sont principalement fondées sur la difficulté à résoudre les problèmes mathématiques (tels que la factorisation des grands nombres) que nous savons parfaitement configurer pour assurer la sécurité de nos services contre les ordinateurs classiques.
Malheureusement, l’état des choses est sur le point d’être renversé, car ces fondations mathématiques ne seront pas capables de résister à la menace de l’informatique quantique. Plus précisément, un ordinateur quantique mettrait à mal la sécurité d’une grande partie de la cryptographie à clé publique utilisée aujourd’hui, puisqu’il serait capable de factoriser un nombre très grand en très peu de temps, grâce à l’algorithme de Shor. Cette menace était suffisamment lointaine à l’époque où l’arrivée des ordinateurs quantiques semblait hors de portée, mais la situation a considérablement changé ces dernières années. La recherche avance rapidement dans ce domaine et il est désormais largement reconnu que cette menace pourrait bientôt devenir réelle, affectant tous les particuliers et toutes les entreprises dans le monde entier. Il est donc important de suivre cette évolution dans le domaine de la cryptographie, et de chercher des solutions alternatives.
Depuis des décennies, nous connaissons des problèmes mathématiques compatibles avec les exigences cryptographiques et capables de résister aux ordinateurs quantiques. Mais il reste encore à les transformer en systèmes cryptographiques réels pouvant être déployés à grande échelle.
L’objectif du projet H2020 PROMETHEUS était de combler l’écart entre la théorie et la pratique, de fournir une meilleure maîtrise aux communautés universitaires, du secteur industriel et de l’État, afin qu’elles soient prêtes pour une transition vers l’ère quantique d’ici 2030. C’est dans ce but que le projet PROMETHEUS s’est concentré sur la cryptographie à base de réseaux euclidiens.
La cryptographie à base de réseaux euclidiens
En quelques mots, les réseaux euclidiens sont des grilles de points régulièrement espacés, généralement dans un espace avec plus de 3 dimensions. En pratique, ils sont représentés par une base, c’est-à-dire un ensemble de vecteurs linéairement indépendants, de telle sorte que le réseau est composé de toutes les combinaisons de nombres entiers linéaires de ces vecteurs. Les réseaux euclidiens s’appuient sur une longue histoire mathématique, et sont pertinents en cryptographie car ils donnent lieu à des problèmes informatiques de nature géométrique. Le problème le plus simple est celui du vecteur le plus court (SVP pour Shortest Vector Problem) : sur un réseau euclidien donné (représenté par une base), trouver son vecteur non nul le plus court (ou une bonne estimation de celui-ci). Bien que facile à résoudre dans la dimension 2, ce problème devient de plus en plus difficile dans les dimensions supérieures.
Intuitivement, la cryptographie à clé publique basée sur les réseaux euclidiens repose sur le principe suivant : une personne génère un réseau euclidien avec une base correcte et garde cette dernière comme clé secrète. Toutefois, elle révèle une base incorrecte du même réseau euclidien comme clé publique. Seule la personne qui connaît la base correcte (la clé secrète) peut résoudre le problème du vecteur le plus court (ou un problème connexe, tel que le problème « Learning with Errors » ou « Short Integer Solution »), et le problème est résolu lors de la conception du cryptosystème pour correspondre à l’opération de déchiffrement (ou celle de signature).
La cryptographie à base de réseaux euclidiens est l’une des alternatives post-quantiques à la cryptographie traditionnelle (basée sur l’algorithme RSA et la cryptographie sur courbes elliptiques). Les autres propositions sont basées sur des outils mathématiques différents, tels que les systèmes de polynômes à plusieurs variables, les codes, les isogénies ou les fonctions de hachage. Mais à ce jour, les solutions les plus prometteuses sont sans doute celles utilisant les réseaux euclidiens. Pour preuve, plusieurs systèmes basés sur les autres problèmes ont récemment été cassés, notamment de façon impressionnante pour les systèmes basés sur des isogénies ou sur des polynômes à plusieurs variables. Cela ne signifie pas la fin de ces familles, mais que leur niveau de maturité n’est aujourd’hui pas assez suffisant.
En effet, les réseaux euclidiens sont les seules solutions dont la sécurité peut être réduite à des problèmes informatiques bien étudiés, tels que « Learning With Errors » ou « Short Integer Solution », tout en permettant de concevoir des protocoles cryptographiques à clé publique efficaces. C’est pourquoi nous avons choisi de nous concentrer sur cette famille dans le projet PROMETHEUS.
Carte d’identification du projet H2020 PROMOTHEUS
À l’origine, l’idée du projet, élaborée par l’ENS de Lyon (en tant que coordinateur) et Orange (en tant que responsable technique), était de travailler et d’améliorer de manière approfondie la maturité de la cryptographie à base de réseaux euclidiens, en tant que système post-quantique. Les objectifs principaux du projet ont ensuite été choisis par un consortium composé de centres de recherche universitaires (ENS de Lyon, Centrum Wiskunde & Informatica, Interdisciplinary Center Herzliya, Royal Holloway University of London, Ruhr Universität Bochum, Universitat Politècnica de Catalunya, université de Rennes 1 et Weizmann Institute of Science), d’une organisation de recherche indépendante (TNO), une PME (Scytl) et de deux entreprises du secteur industriel (Orange et Thales). Plus précisément, les trois objectifs principaux de PROMETHEUS étaient de :
- réaliser une étude complète des fondations mathématiques de la cryptographie à base de réseaux euclidiens,
- fournir des primitives innovantes de cryptographie à base de réseaux euclidiens, et
- protéger la vie privée des individus à l’ère quantique.
Après quatre années de travail, PROMOTHEUS a fourni une vision très précise de la façon dont les services devront évoluer pour être prêts pour 2030, afin de permettre à tous les particuliers et à toutes les entreprises de poursuivre leurs activités numériques en toute sécurité dans le monde quantique. Le projet a donné lieu à plusieurs contributions majeures, sur différents aspects de la recherche et de l’innovation en matière de cryptographie.
Résultats scientifiques
Grâce à une base solide en recherche fondamentale, PROMOTHEUS a généré un nombre assez conséquent de productions scientifiques et plusieurs résultats importants dans le domaine de la cryptographie à base de réseaux euclidiens, ainsi qu’un nombre considérable de publications : 118 à ce jour, toutes parues dans des revues/conférences internationales évaluées par des pairs. Par rapport aux autres projets H2020 dans le domaine de la cryptographie, c’est 1,5 à 5 fois plus ! De plus, parmi nos publications scientifiques, plus de la moitié ont été publiées dans les 3 conférences mondiales les plus reconnues dans le domaine de la cryptographie : Eurocrypt, Crypto, Asiacrypt.
Fondations de la cryptographie à base de réseaux euclidiens : nous avons fourni une étude approfondie des problèmes mathématiques sous-jacents des réseaux euclidiens, menant à la sécurité concrète de ce type de cryptographie. Le nombre de problèmes difficiles est plus important aujourd’hui qu’au début du projet, et nous connaissons également mieux leur degré réel de difficulté grâce à des estimations concrètes. Nous avons également travaillé sur les preuves de sécurité dans le monde quantique, en innovant sur la technique de preuve du modèle de l’oracle aléatoire quantique, et de la sécurité quantique de certaines transformations génériques (par exemple la transformation Fiat-Shamir, ou le passage à un modèle d’attaque à texte chiffré choisi). Cela nous a permis de montrer de manière formelle la façon dont les procédés cryptographiques (les nôtres mais aussi ceux des autres chercheurs en cryptographie) devraient être élaborés afin de contrer un attaquant doté de capacités quantiques. Nous avons par ailleurs publié des articles et fourni les premières preuves de concept sur la façon d’implémenter un syst-me cryptographique à base de réseaux euclidiens en toute sécurité, offrant un ensemble de contremesures pour se défendre des attaques dites par canaux auxiliaires.
Primitives de cryptographie à base de réseaux euclidiens : nous avons conçu et mis en œuvre un ensemble de constructions de base liés aux signatures numériques avec des fonctionnalités supplémentaires, à des nouveaux procédés de chiffrement et à des preuves à divulgation nulle de connaissance servant à démontrer la véracité de certaines affirmations mathématiques utilisées dans un protocole cryptographique. Ces primitives ont été fondamentales pour notre travail sur la normalisation et pour la conception de nos prototypes de cas d’usage (voir ci-dessous). Nous avons notamment entièrement reconceptualisé la notion de signature aveugle dans le contexte des réseaux euclidiens, pour laquelle un standard ISO/IEC existe, et qui est particulièrement pertinent pour protéger la vie privée des individus. Des preuves montrent que la sécurité du procédé peut être réduite mathématiquement à la difficulté de résoudre un problème de réseau euclidien difficile (voir ci-dessus), ce qui atteste de la solidité du système que nous avons conçu.
Protocoles de cryptographie à base de réseaux euclidiens : enfin, nous avons élaboré des protocoles cryptographiques liés à des cas d’utilisation concrets. Plus précisément, nous avons créé le premier système de paiement sécurisé et résistant aux ordinateurs quantique, qui protège la vie privée des individus. Nous avons montré que la sécurité de toutes les constructions antérieures n’était pas attestée, et nous avons proposé une conception générique et une construction concrète entièrement sécurisées. Nous avons également étudié et proposé plusieurs solutions pour le vote électronique basé sur les réseaux euclidiens. Notre travail a également mené à la première mise en œuvre d’un système d’accréditations anonymes basées sur les réseaux euclidiens, une primitive utilisée pour minimiser la quantité de données sensibles fournies par un individu pour interagir avec un prestataire de services.
Création de valeurs
Normalisation : l’un de nos résultats les plus importants au cours du projet PROMETHEUS est liée à la normalisation. Peu de temps après la soumission du projet, le National Institute of Standards and Technology (NIST) aux États-Unis a organisé un concours pour définir les futures normes de la cryptographie post-quantique. 4 ans après le début du concours et 69 propositions initiales, le NIST a finalement annoncé en juin 2022 les 4 futures normes en matière de cryptographie qui seront utilisées au quotidien. Parmi ces systèmes, 3 d’entre eux ont été initiés par les partenaires de PROMETHEUS :
- CRYSTALS-KYBER pour le chiffrement à clé publique et les algorithmes d’échange de clé,
- CRYSTALS-DILITHIUM et Falcon pour les signatures numériques.
Ce résultat a été rendu possible grâce au travail sur ce projet, ainsi qu’aux publications qui ont continuellement soutenu nos propositions ou qui ont démontré les faiblesses d’autres systèmes, mais également aux implémentations que nous avons réalisées pour démontrer la pertinence des solutions du consortium.
Librairies open source : un autre aboutissement important de ce projet est la création de plusieurs bibliothèques open source dédiées à la cryptographie post-quantique. Nous avons d’abord fourni à la communauté scientifique plusieurs déploiements logiciels et hardwares de primitives de cryptographie à base de réseaux euclidiens (signatures numériques et mécanismes de chiffrement). Notre recherche a aussi donné lieu à la création et la maintenance de bibliothèques (LWE-estimator, Leaky-LWE-estimator and NTRUFatigue-estimator) dédiées à l’estimation des meilleurs paramètres à utiliser en cryptographie à base de réseaux euclidiens, en prenant en compte les attaques les plus connues et l’impact sur l’efficacité. Ces outils open source sont d’une importance capitale pour aider :
- la communauté universitaire à concevoir des procédés cryptographiques à base de réseaux euclidiens,
- l’industrie à choisir des paramètres concrets en fonction de ses propres exigences et des dernières avancées en matière d’analyse cryptographique,
- tout le monde à mieux comprendre les attaques contre la cryptographie à base de réseaux euclidiens.
Effet sociétal
Cas d’utilisation : pour démontrer la pertinence de nos recherches, PROMETHEUS a finalement mis en lumière la maturité de la cryptographie à base de réseaux euclidiens en travaillant sur les exigences concrètes de quatre démonstrateurs dans un environnement pertinent (connu comme étant un niveau 5 de maturité technologique). Ces cas d’utilisation ont été choisis pour montrer comment protéger la vie quotidienne des individus à l’ère quantique.
Système de vote électronique post-quantique – nous avons fourni le premier prototype de vote électronique post-quantique. En raison de son utilisation de plus en plus fréquente au niveau institutionnel ou dans les entreprises et les associations, le vote électronique est particulièrement sensible à la menace des ordinateurs quantiques. En effet, l’un des risques associés concerne le problème du « Stocker maintenant, déchiffrer plus tard » : une personne mal intentionnée stocke les votes numériques d’une élection de nos jours, et attend l’arrivée des ordinateurs quantiques afin de casser la sécurité du système cryptographique utilisé, et ainsi connaître le vote de chaque électeur. Le travail accompli par PROMETHEUS sur ce sujet permettrait de déployer des solutions pour contrer ce type d’attaque plus rapidement.
Système de paiement à résistance quantique respectueux de la confidentialité – le deuxième cas d’utilisation était axé sur les consommateurs et leurs préoccupations concernant la protection de leurs paiements pour des biens ou des services dans leur vie numérique. Grâce à un système de paiement numérique résistant aux ordinateurs quantiques, dont la solution cryptographique a été développée au cours du projet, notre prototype empêche le suivi des achats des clients (sauf en cas de fraude), même avec l’utilisation d’un ordinateur quantique. Ce système a fait l’objet de discussions avec la CNIL et le Comité européen de la protection des données (CEPD) pour les aider à définir leurs exigences sur un futur système de paiement numérique européen avec protection de la vie privée.
Système d’authentification quantiquement sûr respectueux de la vie privée – le troisième prototype montre en pratique comment les systèmes d’information d’identification anonymes que nous avons conçus peuvent être utilisés dans un produit réel. Ce type de système permet à un individu de minimiser la quantité d’informations personnelles (âge, lieu de résidence, emploi, etc.) qu’il révèle lorsqu’il souhaite accéder à des services en ligne ou effectuer des démarches administratives. Ce système pourrait constituer la base d’une future carte d’identité numérique européenne respectueuse de la vie privée.
Système de collecte d’informations sur les cybermenaces protégeant les données sur le long terme – nous avons également conçu un prototype de système de collecte d’informations sur les cybermenaces permettant à plusieurs entreprises de protéger leurs données sensibles sur le long terme, tout en les partageant entre elles de façon sécurisée afin de détecter des cyberattaques ensemble de manière plus efficace.
Agences de sécurité : nous avons participé à des échanges scientifiques avec des agences nationales dédiées à la sécurité et à la protection de la vie privée (l’ANSSI et la CNIL) concernant la transition vers la cryptographie post-quantique et le travail de PROMETHEUS sur des primitives cryptographiques basiques et avancées. Plus spécifiquement, nous avons abordé la position de l’ANSSI vis-à-vis des primitives post-quantiques et sa stratégie pour la transition vers les systèmes post-quantiques entre maintenant et 2030. Nous avons également présenté notre travail sur les protocoles avancés, les difficultés que nous avons rencontrées et les solutions proposées. Nous avons participé à deux réunions avec la CNIL : l’une consacrée à l’exploitation concrète de la monnaie électronique, et l’autre à la maturité actuelle de la cryptographie post-quantique respectueuse de la vie privée.
Conclusion
PROMETHEUS a accompli un travail fondamental pour améliorer la maturité de la cryptographie post-quantique, et plus particulièrement la cryptographie à base de réseaux euclidiens. Cela pourrait amener à penser que la majeure partie du travail a été effectuée. Malheureusement il reste encore beaucoup à faire avant de pouvoir exploiter concrètement ces résultats. En effet, le chemin à parcourir entre la conception de ces protocoles et leur mise en œuvre concrète est considérable. Plusieurs défis techniques doivent encore être relevés en matière d’intégration des mécanismes cryptographiques dans des produits réels, alors que ceux-ci n’étaient jusqu’à maintenant que le sujet d’études théoriques. C’est le travail qui nous attend dans les années à venir.
