La cryptographie sur les réseaux est l’une des approches les plus compétitives pour protéger la confidentialité, dans les applications actuelles et l’ère post-quantique. Le problème central qui sert de fondement de complexité de la cryptographie sur réseaux est Learning with Errors (LWE). Il consiste à résoudre un système d’équations bruité, linéaire et surdéterminé. Ce problème est au moins aussi difficile que les problèmes standards portant sur les réseaux, tels que le décodage à distance bornée (BDD pour Bounded Distance Decoding) et le problème du vecteur le plus court unique (uSVP pour unique Shortest Vector Problem). Tous ces problèmes sont conjecturés difficiles à résoudre, même avec un ordinateur quantique de grande échelle. En particulier, le meilleur algorithme connu pour résoudre ces problèmes, BKZ, est très coûteux. Dans cette thèse, nous étudions les relations de difficulté entre BDD et uSVP, la difficulté quantique de LWE et les performances pratiques de l’algorithme BKZ. Tout d’abord, nous donnons une relation de difficulté plus étroite entre BDD et uSVP. Plus précisément, nous améliorons la réduction de BDD à uSVP d’un facteur √2, comparément à celle de Lyubashevsky et Micciancio. Ensuite, Nous apportons un nouvel élément à la conjecture que LWE est quantiquement difficile. Concrètement, nous considérons une version relâchée de la version quantique du problème du coset dièdral et montrons une équivalence computationnelle entre LWE et ce problème. Enfin, nous proposons un nouveau simulateur pour BKZ. Dans ce dernier travail, nous proposons le premier simulateur probabiliste pour BKZ, qui permet de prévoir le comportement pratique de BKZ très précisément.
La cryptographie sur les réseaux est l’une des approches les plus compétitives pour protéger la confidentialité, dans les applications actuelles et l’ère post-quantique. Le problème central qui sert de fondement de complexité de la cryptographie sur réseaux est Learning with Errors (LWE). Il consiste à résoudre un système d’équations bruité, linéaire et surdéterminé. Ce problème est au moins aussi difficile que les problèmes standards portant sur les réseaux, tels que le décodage à distance bornée (BDD pour Bounded Distance Decoding) et le problème du vecteur le plus court unique (uSVP pour unique Shortest Vector Problem). Tous ces problèmes sont conjecturés difficiles à résoudre, même avec un ordinateur quantique de grande échelle. En particulier, le meilleur algorithme connu pour résoudre ces problèmes, BKZ, est très coûteux. Dans cette thèse, nous étudions les relations de difficulté entre BDD et uSVP, la difficulté quantique de LWE et les performances pratiques de l’algorithme BKZ. Tout d’abord, nous donnons une relation de difficulté plus étroite entre BDD et uSVP. Plus précisément, nous améliorons la réduction de BDD à uSVP d’un facteur √2, comparément à celle de Lyubashevsky et Micciancio. Ensuite, Nous apportons un nouvel élément à la conjecture que LWE est quantiquement difficile. Concrètement, nous considérons une version relâchée de la version quantique du problème du coset dièdral et montrons une équivalence computationnelle entre LWE et ce problème. Enfin, nous proposons un nouveau simulateur pour BKZ. Dans ce dernier travail, nous proposons le premier simulateur probabiliste pour BKZ, qui permet de prévoir le comportement pratique de BKZ très précisément.
Contributions aux fondements de complexité de la cryptographie sur réseaux La cryptographie sur les réseaux est l’une des approches les plus compétitives pour protéger la confidentialité, dans les applications actuelles et l’ère post-quantique. Le problème central qui sert de fondement de complexité de la cryptographie sur réseaux est Learning with Errors (LWE). Il consiste à résoudre un système d’équations bruité, linéaire et surdéterminé. Ce problème est au moins aussi difficile que les problèmes standards portant sur les réseaux, tels que le décodage à distance bornée (BDD pour Bounded Distance Decoding) et le problème du vecteur le plus court unique (uSVP pour unique Shortest Vector Problem). Tous ces problèmes sont conjecturés difficiles à résoudre, même avec un ordinateur quantique de grande échelle. En particulier, le meilleur algorithme connu pour résoudre ces problèmes, BKZ, est très coûteux. Dans cette thèse, nous étudions les relations de difficulté entre BDD et uSVP, la difficulté quantique de LWE et les performances pratiques de l’algorithme BKZ. Tout d’abord, nous donnons une relation de difficulté plus étroite entre BDD et uSVP. Plus précisément, nous améliorons la réduction de BDD à uSVP d’un facteur √2, comparément à celle de Lyubashevsky et Micciancio. Ensuite, Nous apportons un nouvel élément à la conjecture que LWE est quantiquement difficile. Concrètement, nous considérons une version relâchée de la version quantique du problème du coset dièdral et montrons une équivalence computationnelle entre LWE et ce problème. Enfin, nous proposons un nouveau simulateur pour BKZ. Dans ce dernier travail, nous proposons le premier simulateur probabiliste pour BKZ, qui permet de prévoir le comportement pratique de BKZ très précisément.
Cette thèse de doctorat porte principale ment sur le problème d’apprentissage avec erreurs, appelé Learning With Errors (LWE). Il s’agit d’une composante essentielle de la cryptographie à base de réseaux, qui fait partie des candidats les plus prometteurs pour remplacer les protocoles cryptographiques actuels lorsque des ordinateurs quantiques à grande échelle seront disponibles. Dans cette thèse, nous étudions la difficulté théoriques des variantes algébriquement structurées de LWE qui sont utilisées dans des protocoles efficaces. D’abord, nous prouvons que le problème Module Learning With Errors (M-LWE) ne devient pas significativement plus facile à résoudre, même si le secret sous-jacent est remplacé par un vecteur binaire. Ensuite, nous présentons une réduction classique au problème M-LWE, ce qui renforce notre confiance dans sa valeur pour la cryptographie. De plus, nous définissons une nouvelle hypothèse de difficulté, le problème MP-LWR (Middle-Product Computational Learning With Rounding), qui hérite des avantages de deux variantes existantes de LWE. Enfin, nous étudions des problèmes liés à la matrice partielle de Vandermonde. Il s’agit d’une source récente d’hypothèses de difficulté pour la cryptographie à base de réseaux et son étude rigoureuse est primordiale pour gagner en fiabilité. Finalement, nous montrons que les nouvelles hypothèses de difficulté introduites auparavant servent à la construction de schémas de chiffrement à clé publique efficaces. D’une part, nous concevons un nouveau schéma de chiffrement, dont la sécurité est assurée par la difficulté du problème MP-CLWR. D’autre part, nous modifions un schéma de chiffrement existant pour lui fournir une preuve de sécurité basée sur deux problèmes de Vandermonde partiels explicitement énoncés.
Difficultés de Problèmes de Réseaux Structurés pour la Cryptographie Post-Quantique La sécurité des protocoles cryptographiques repose sur la difficulté présumée de problèmes algorithmiques. Parmi ceux qui ont été identifiés jusque-là, les meilleurs problèmes pouvant servir de fondation à une cryptographie résistante aux ordinateurs quantiques sont issus des réseaux euclidiens. Les réseaux euclidiens sont une structure mathématique définie comme un ensemble de vecteurs de l’espace générés par les combinaisons entières d’un nombre fini de vecteurs réels linéairement indépendants (sa base). Un exemple typique de problème de sécurité relié est le Shortest Vector Problem (SVP). Étant donné une base d’un réseau euclidien en dimension n, trouver un vecteur court non nul. Pour des raisons d’efficacité, ces problèmes sont restreints à des réseaux issus de la théorie des nombres, dit structurés. Les hypothèses de sécurité relatives à ces réseaux particuliers étant différentes de celles des réseaux non structurés, il est nécessaire de les étudier spécifiquement, c’est l’objet de cette thèse. Nous avons étudié le cas des modules NTRU et uSVP en rang 2, prouvant que le problème SVP est équivalent sur ces deux familles de réseaux. Nous montrons également une réduction pire-cas vers cas-moyens pour les réseaux uSVP en rang 2. Ensuite nous avons démontré que résoudre SVP sur un idéal premier de petite norme n’était pas plus facile que de résoudre SVP sur n’importe quel idéal.
Difficulté théorique des variantes algébriques du problème learning with errors Cette thèse de doctorat porte principale ment sur le problème d’apprentissage avec erreurs, appelé Learning With Errors (LWE). Il s’agit d’une composante essentielle de la cryptographie à base de réseaux, qui fait partie des candidats les plus prometteurs pour remplacer les protocoles cryptographiques actuels lorsque des ordinateurs quantiques à grande échelle seront disponibles. Dans cette thèse, nous étudions la difficulté théoriques des variantes algébriquement structurées de LWE qui sont utilisées dans des protocoles efficaces. D’abord, nous prouvons que le problème Module Learning With Errors (M-LWE) ne devient pas significativement plus facile à résoudre, même si le secret sous-jacent est remplacé par un vecteur binaire. Ensuite, nous présentons une réduction classique au problème M-LWE, ce qui renforce notre confiance dans sa valeur pour la cryptographie. De plus, nous définissons une nouvelle hypothèse de difficulté, le problème MP-LWR (Middle-Product Computational Learning With Rounding), qui hérite des avantages de deux variantes existantes de LWE. Enfin, nous étudions des problèmes liés à la matrice partielle de Vandermonde. Il s’agit d’une source récente d’hypothèses de difficulté pour la cryptographie à base de réseaux et son étude rigoureuse est primordiale pour gagner en fiabilité. Finalement, nous montrons que les nouvelles hypothèses de difficulté introduites auparavant servent à la construction de schémas de chiffrement à clé publique efficaces. D’une part, nous concevons un nouveau schéma de chiffrement, dont la sécurité est assurée par la difficulté du problème MP-CLWR. D’autre part, nous modifions un schéma de chiffrement existant pour lui fournir une preuve de sécurité basée sur deux problèmes de Vandermonde partiels explicitement énoncés.
L'émergence de l'ordinateur quantique impose protéger nos systèmes informatiques face à ces nouvelles attaques quantiques. De nombreux schémas cryptographiques post-quantiques reposent sur la difficulté de résoudre des problèmes provenant des théories des réseaux euclidiens et de codes. Dans cette thèse, nous étudions la complexité du problème de trouver un vecteur court (SVP) dans un réseau. Nous améliorons l'attaque quantique contre SVP grâce à un nouvel algorithme de crible utilisant des marches quantiques et des techniques de filtrage. Nous proposons aussi des algorithmes de k-crible atteignant de meilleurs compromis temps-mémoire en introduisant une nouvelle technique de filtrage adaptée au k-crible. Nous nous intéressons aussi à la complexité du problème de décodage, sur lequel repose notamment la signature électronique Wave. Nous décrivons une attaque quantique pour contrefaire des signatures, et estimons sa sécurité face aux meilleurs attaques classiques et quantiques connues.
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.