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.
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é 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.
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.
Cryptographie classique et post-quantiqueCes nouvelles solutions doivent s'appuyer sur des problèmes mathématiques qui ne sont pas vulnérables à l'avantage qu'ont les ordinateurs quantiques sur les primitives cryptographiques se basant sur des problèmes mathématiques dits "standards".Ces outils mathématiques "standards" se composent notamment du cryptosystème RSA [RSA78] (du nom de ses auteurs Rivest, Shamir et Adleman) qui repose sur le problème de la factorisation, ou du cryptosystème El-Gamal reposant sur le problème du logarithme discret.Dans le cas des cryptosystèmes de type RSA, la clé secrète est composée entre autre de deux nombres premiers p et q dont leur produit N = p×q fait partie de la clé publique.Un attaquant qui arriverait donc à factoriser le nombre N pour retrouver les deux nombres premiers p et q, pourrait attaquer la sécurité des schémas de type RSA.Concernant les cryptosystèmes basés sur le logarithme discret, on considère un groupe G bien choisi, le plus souvent d'ordre premier p.On va ensuite choisir aléatoirement un entier a comme partie de la clé secrète et son pendant publique qui lui est associé est g a avec g un élément choisi aléatoirement dans le groupe G. On définit alors le problème du logarithme discret, demandant de retrouver l'entier a à partie de l'élément g a appartenant au groupe G.Ces deux types de problèmes ont été à l'origine de nombreux schémas cryptographiques sûrs et proposant une efficacité très attractive mais, comme énoncé précédemment, ils seront vulnérables dans une ère post-quantique.En effet, conserver leur sécurité impli- ContributionsDans la suite de cette introduction, je vais détailler les contributions que j'ai pu apportées durant mes 3 années de thèses, qui concernent principalement la conception de schémas cryptographiques respectueux de la vie privée, ainsi que l'adaptation en cas Signatures de groupesMa première contribution concerne la construction d'une signature de groupe sur les réseaux euclidiens, à laquelle nous ajoutons quelques propriétés attractives.Par définition, une signature de groupe est un schéma permettant à un groupe d'utilisateurs de signer au nom de ce même groupe, tout en restant anonyme parmi ses membres.Elles fournissent une caractéristique supplémentaire qui est de permettre "l'ouverture" d'une signature pour en retrouver le membre du groupe qui en est à l'origine.Ces schémas ont de nombreuses applications dans la vie courante.Prenons par exemple un cas où une personne doit prouver qu'elle a un certain âge (par exemple moins de 25 ans pour pouvoir prétendre à une réduction), il suffirait qu'elle produise sa carte d'identité qui contient sa date de naissance et donc son âge.Cependant en produisant ainsi sa carte d'identité, elle fournit par la même occasion son nom, son adresse..., alors que seul le fait qu'elle appartient au groupe des moins de 25 ans est nécessaire.Les signatures de groupes permettent donc d'éviter de tels désagréments.Il existe à ce jour de nombreux schémas de signature de groupe, mais les plus efficaces d'entre eux s'appuient sur des hypothèses qui ne résisteraient pas à un ordinateur quantique, tels que le logarithme discret défini précédemment.C'est pourquoi depuis une dizaine d'années, un grand nombre de constructions basées sur les réseaux euclidiens ont été conçues ([Gol+10; Lag+13; Lan+14; Lib+16b; Lin+17]...).Ces constructions doivent cependant se plier à l'inefficacité, sur les réseaux, des preuves de connaissance à divulgation nulle de connaissance nécessaires pour de telles constructions dans le modèle habituel de Bellare et al [BMW03].Cependant en 2019, un nouveau schéma publié à Eurocrypt par Kastumata et Yamada [KY19] s'écarte de ce modèle habituel.Leur construction s'appuie sur des primitives plus récentes telles que les signatures basées sur les attributs pour court-circuiter les problèmes d'inefficacité, en plus de reposer sur un modèle de sécurité plus commun.À partir de cette nouvelle construction nous proposons un schéma de signature de groupe basé sur les réseaux qui bénéficie des mêmes avantages que le schéma de [KY19] et nous ajoutons en plus une nouvelle propriété appelée forward security.Celle-ci permet de diviser le temps en plusieurs périodes, de sorte que les clés secrètes de tous les membres du groupe sont mises à jour à chaque nouvelle période de temps sans possibilité de récupérer Signature aveugleLes signatures aveugles ont été introduites en 1982 par Chaum [Cha82] pour le cas d'usage précis de la monnaie électronique.L'idée d'une signature aveugle est la suivante: un utilisateur veut générer une signature sur un message de son choix, cependant il ne possède pas la clé secrète lui permettant de générer une telle signature.Pour palier ce problème, il a la possibilité d'interagir avec une autorité qui possède cette clé secrète et qui est alors vu comme un signeur.Cependant l'utilisateur requiert que la signature qu'il va sortir à la fin de l'interaction avec le signeur ne puisse pas être tracée par ce dernier.Pour en revenir au cas d'usage de la monnaie électronique, ce type de schéma permet donc à un utilisateur de faire certifier de la monnaie électronique à une autorité (une banque par exemple), sans que celle-ci puisse retrouver l'identité de l'utilisateur lorsque celui-ci la dépense.Concernant les constructions existantes, elles sont nombreuses et très efficaces sur la cryptographie "classique".Nous pouvons notamment citer le schéma Blind RSA [Fer93] qui se base sur le cryptosystème RSA, tandis que l'histoire des signatures aveugles sur les réseaux euclidiens est bien plus complexes.Tout d'abord il n'existe qu'un seul modèle de construction basé sur un schéma d'identification de Lyubashevsky [Lyu08].Ce modèle requiert 3 échanges entre l'utilisateur et le signeur, comme d'autres schémas tel que Okamoto-Schnorr [Oka92], à contrario d'autres constructions comme blind RSA qui n'en demandent que 2.De plus toutes les constructions sur les réseaux euclidiens ont vu leur preuve de sécurité invalidées par un papier de Hauck et al [Hau+20] publié à Crypto 2020.En effet pour prouver qu'un utilisateur malhonnête ne peut pas générer plus de signatures qu'autorisées, une propriété appelée one-more unforgeability est nécessaire.Une modèle de preuve a été proposé par Pointcheval et Stern [PS00] pour des constructions basées sur des groupes finis, dans lesquels un élément secret était choisi aléatoirement dans tout le groupe.La différence sur les réseaux euclidiens vient du fait qu'une clé secrète est habituellement un petit élément de l'ensemble considéré, ce qui interdit toute adaptation directe sur les réseaux euclidiens de la preuve de Pointcheval et Stern.Dans notre construction, nous revenons sur cette preuve et sur la solution apportée par Hauck et al. [Hau+20] qui souffre d'un manque d'efficacité.Concernant notre construction, notre sécurité repose sur une conjecture qui n'a pas été prouvée.Tout d'abord, notre solution gagne en efficacité en utilisant l'avantage de distributions gaussiennes sur des distributions uniformes.De plus, nous utilisons des outils tels que les trappes sur les réseaux euclidiens pour effacer toute trace d'abandon durant le protocole de signature aveugle, notre construction étant la seule n'ayant pas recours aux abandons, qui est un impact négatif sur l'efficacité.Finalement, nous proposons une variante appelée signature partiellement aveugle, qui permet à l'utilisateur et au signeur d'inclure une information publique, sur laquelle ils se sont mis d'accord en amont de la génération de la signature.Notre construction n'entraîne quasiment aucun coût supplémentaire par rapport à la signature aveugle.Ce travail est décrit dans le chapitre 5 de cette thèse.
Dans cette thèse, nous étudions la cryptographie classique et quantique dans des modèles quantiques idéalisés. Des travaux antérieurs ont montré que les ressources quantiques peuvent être utilisées pour réaliser des tâches cryptographiques qui sont prouvées ou supposées impossibles dans le paradigme classique. Dans cette thèse, nous prouvons tout d'abord des bornes inférieures sur l'efficacité de n'importe quel algorithme quantique cherchant une couverture par sous-ensembles d'une fonction aléatoire, un problème conjecturé difficile et utilisé pour évaluer la sécurité du schéma de signature post-quantique SPHINCS+. Ensuite, nous étendons les résultats d'impossibilité existants concernant la construction de schémas de chiffrement à clé publique dans le modèle quantique de l'oracle aléatoire, en montrant qu'un type plus général de chiffrement à clé publique n'existe pas dans ce modèle. Nous étudions ensuite des hypothèses quantiques pour la cryptographie qui semblent plus faibles que les fonctions à sens unique, à savoir les générateurs d'états quantique pseudoaléatoires, ainsi que leur relation avec les schémas quantiques de chiffrement à clé publique et de signature, en clarifiant et en améliorant les constructions et les preuves d'impossibilité déjà existantes. Enfin, nous établissons l'importance de la taille des états quantique pseudoaléatoires en prouvant qu'un état quantique pseudoaléatoire ne peut pas être compressé, et nous progressons vers la démonstration qu'il ne peut pas non plus être amplifié.
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.