Conception d'algorithmes de signatures avancées post-quantiques
Corentin Jeudy · theses.fr (ABES) · 2024
Go to Contentsconsiste essentiellement à trouver une base B ⋆ qui soit suffisamment plus courte que la base B donnée en entrée.En 1982, Lenstra, Lenstra et Lovàsz [LLL82] ont introduit l'un des premiers algorithmes de réduction pour les réseaux euclidiens : le célèbre algorithme LLL, qui vise à réduire la base d'un réseau tout en ayant des vecteurs les plus orthogonaux possibles.Il peut ensuite être utilisé pour résoudre SVP γ , mais ne fonctionne en un temps raisonnable que lorsque γ est exponentiel en d.Le problème est en effet supposé difficile pour γ polynomial en d, même en ayant accès à des ressources quantiques.Malgré cette supposée résistance quantique, SVP γ n'est pas très adapté à la conception d'algorithmes cryptographiques car il s'agit d'un problème dit pire-cas, c'est-à-dire qu'il est facile pour de nombreux réseaux mais difficile pour les pires d'entre eux.En 1996, Ajtai [Ajt96] publia un article fondamental sur l'utilisation des réseaux euclidiens en cryptographie.Dans cet article, Ajtai introduisit un nouveau problème de réseau appelé Short Integer Solution (SIS) et donna la première réduction pire-cas moyen-cas d'une variante de SVP γ à SIS.Cela a d'énormes conséquences en cryptographie car les constructions basées sur ce problème moyen-cas reposent désormais sur la difficulté des pires instances du problème de réseau sous-jacent, et non sur les instances moyennes.Cela signifie que si la construction est cassée, le problème intermédiaire SIS peut être facilement résolu en moyenne et donc que toutes les instances du problème de réseau sous-jacent peuvent également être résolues facilement, y compris les plus difficiles.En 2005, Regev [Reg05] présenta alors un autre problème intermédiaire qui bénéficie également des hypothèses de difficulté dans le pire des cas.Il décrivit le problème Learning With Errors (LWE) et donna une réduction (quantique) des problèmes difficiles sur les réseaux à LWE.Il présenta également un système de chiffrement à clé publique dont la sécurité repose sur la difficulté de LWE.Depuis, de nombreuses constructions basées sur ces problèmes ont vu le jour, ainsi que de meilleures réductions.Certaines questions ouvertes ont également été résolues grâce aux progrès de la cryptographie sur les réseaux euclidiens, comme le chiffrement complètement homomorphe (FHE pour Fully Homomorphic Encryption) [BGV12, BV14, DM15], qui a longtemps été considéré comme impossible.En 2009, Gentry [Gen09] présenta en effet le premier schéma de FHE basé sur des réseaux euclidiens, en tant que preuve de concept.Bien qu'attrayants en raison de la base théorique qu'ils fournissent, les problèmes originaux SIS et LWE ont depuis été modifiés sous de nombreux aspects afin d'offrir une meilleure efficacité, par exemple à travers des variantes algébriques [LPR10, LS15, PP19].Les efforts déployés pour accroître la confiance en ces variantes modifiées, soit par des preuves théoriques, soit par des évaluations cryptanalytiques, ont considérablement contribué au développement de la cryptographie sur les réseaux euclidiens et sont toujours en cours.Tous ces arguments historiques constituent quelques-unes des raisons pour lesquelles les réseaux euclidiens sont utilisés en cryptographie : ce sont des objets simples, qui s'avèrent particulièrement efficaces si la structure et les paramètres sont bien choisis; ils offrent une sécurité prouvable pour les constructions grâce aux problèmes de réseaux sous-jacents; ils offrent la possibilité de concevoir une grande variété de mécanismes cryptographiques; et enfin, les problèmes de réseaux sont conjecturés comme étant résistants aux attaques quantiques.