Signatures post-quantiques à partir de techniques de calcul multipartite Le développement actuel des ordinateurs quantiques pousse la communauté cryptographique à mettre au point de nouveaux cryptosystèmes dont la sécurité se fonde sur la difficulté à résoudre des problèmes cryptographiques résistant au calcul quantique. Dans le cadre de cette thèse, nous nous sommes focalisés sur la conception de schémas de signatures électroniques construits à partir de preuves à divulgation nulle de connaissance (zero-knowledge proofs of knowledge). Plus précisément, nous nous sommes intéressés au paradigme “MPC-in-the-Head” (littéralement, “calcul-multipartite-dans-la-tête”) qui fournit une méthode générique de construire de telles preuves en utilisant des techniques de calcul multipartite sécurisé. Nous proposons plusieurs nouveaux schémas de signatures utilisant le paradigme “MPC-in-the-Head”. La plupart d’entre eux sont compétitifs avec les schémas existants dans l’état de l’art post-quantique. Ils produisent des signatures ayant des tailles entre 5 et 20 kylo-octets (pour un niveau de sécurité de 128 bits) et possèdent de très petites clés (de moins de 200 octets). Les problèmes difficiles sur lesquels la sécurité de ces schémas se fonde sont très variés. Certains schémas s’appuient sur des hypothèses de sécurité issues de la théorie des codes correcteurs d’erreurs, telle que celle sur la difficulté à résoudre le problème de décodage par syndrome pour des codes linéaires aléatoires. Les autres schémas s’appuient sur la difficultés à résoudre un système d’équations quadratiques, le problème de la somme de sous-ensembles ou le problème MinRank. Nous avons également mis au point deux nouvelles techniques de MPC-in-the-Head. La première vise à gérer efficacement les situations où le secret est de petite taille avec un grand modulus. La seconde consiste en une nouvelle méthode pour transformer un protocole de calcul multipartite en preuve de divulgation nulle de connaissance. Cette nouvelle transformation offre des nouveaux compromis entre coût de communication et temps de calcul. En particulier, elle permet de produire des algorithmes de vérification très rapides. Plusieurs soumissions à l’appel du NIST pour des schémas de signatures post-quantiques supplémentaires s'appuient (parfois partiellement) sur des idées développées dans le cadre de cette thèse.
Signatures post-quantiques à partir de techniques de calcul multipartite Le développement actuel des ordinateurs quantiques pousse la communauté cryptographique à mettre au point de nouveaux cryptosystèmes dont la sécurité se fonde sur la difficulté à résoudre des problèmes cryptographiques résistant au calcul quantique. Dans le cadre de cette thèse, nous nous sommes focalisés sur la conception de schémas de signatures électroniques construits à partir de preuves à divulgation nulle de connaissance (zero-knowledge proofs of knowledge). Plus précisément, nous nous sommes intéressés au paradigme “MPC-in-the-Head” (littéralement, “calcul-multipartite-dans-la-tête”) qui fournit une méthode générique de construire de telles preuves en utilisant des techniques de calcul multipartite sécurisé. Nous proposons plusieurs nouveaux schémas de signatures utilisant le paradigme “MPC-in-the-Head”. La plupart d’entre eux sont compétitifs avec les schémas existants dans l’état de l’art post-quantique. Ils produisent des signatures ayant des tailles entre 5 et 20 kylo-octets (pour un niveau de sécurité de 128 bits) et possèdent de très petites clés (de moins de 200 octets). Les problèmes difficiles sur lesquels la sécurité de ces schémas se fonde sont très variés. Certains schémas s’appuient sur des hypothèses de sécurité issues de la théorie des codes correcteurs d’erreurs, telle que celle sur la difficulté à résoudre le problème de décodage par syndrome pour des codes linéaires aléatoires. Les autres schémas s’appuient sur la difficultés à résoudre un système d’équations quadratiques, le problème de la somme de sous-ensembles ou le problème MinRank. Nous avons également mis au point deux nouvelles techniques de MPC-in-the-Head. La première vise à gérer efficacement les situations où le secret est de petite taille avec un grand modulus. La seconde consiste en une nouvelle méthode pour transformer un protocole de calcul multipartite en preuve de divulgation nulle de connaissance. Cette nouvelle transformation offre des nouveaux compromis entre coût de communication et temps de calcul. En particulier, elle permet de produire des algorithmes de vérification très rapides. Plusieurs soumissions à l’appel du NIST pour des schémas de signatures post-quantiques supplémentaires s'appuient (parfois partiellement) sur des idées développées dans le cadre de cette thèse.
Cryptographie post-quantique pour la protection de la vie privée Ces dernières années la cryptographie a été chamboulée par l'arrivée des ordinateurs quantiques. En effet ceux-ci possèdent un très fort avantage pour casser les schémas cryptographique utilisés actuellement dans la quasi-totalité des communications sécurisées. Nous proposons dans cette thèse plusieurs constructions cryptographiques basées sur des outils mathématiques résistants à ces ordinateurs quantique, que sont les réseaux euclidiens. Tout d'abord nous construisons une signature de groupe, permettant à chaque membre composant un groupe donné de signer au nom du groupe tout en conservant son anonymat. Nous rajoutons une propriété supplémentaire qui est la "forward secrecy" qui sépare le temps en périodes durant lesquelles les clés secrètes des utilisateurs sont mises à jour. Nous proposons également un schéma de signature aveugle qui permet à un utilisateur de générer une signature sur un message de son choix de manière interactive avec un signeur qui possède la clé de signature. Nous améliorons l'état-de-l'art en proposant un schéma sans abandon et avec une sécurité plus efficace. Enfin, comme cas d'usage de la signature aveugle nous construisons un schéma de vote électronique à partir de cette primitive.
Sécurité des protocoles cryptographiques fondés sur la théorie des codes correcteurs d'erreurs Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits.
Arguments à divulgation nulle de connaissance via du calcul réparti sécurisé Cette thèse a pour but d'étudier les arguments à divulgation nulle de connaissance, une primitive cryptographique qui permet de prouver un énoncé tout en ne révélant rien d'autre que sa vérité (nous pouvons l'appeler preuve au lieu d'argument en fonction du modèle de sécurité). Plus précisément, nous nous concentrons sur une famille d'arguments dont la construction est basée sur le calcul multipartite sécurisé. Il est bien connu que, pour toute fonctionnalité, il existe un protocole multipartite sécurisé pour la calculer. Prenons une fonction générique à sens unique f, et un protocole multipartite sécurisé calculant f, il a été montré assez récemment que nous pouvons construire un argument à divulgation nulle de connaissance pour le problème NP de trouver une pré-image de f. Cette construction n'était considérée que comme théorique jusqu'à il y a quelques années, et notre travail contribue à l'émergence de nouvelles techniques ainsi que d'applications efficaces dans ce paradigme. En guise d'amuse-gueule, nous développons des protocoles simples qui améliorent de manière significative la complexité en communication pour certains problèmes bien connus. Notre première contribution substantielle, avec un désir de partager des petits éléments, est l'introduction d'un partage sur les entiers qui est intégré de manière sûre dans nos protocoles avec un rejet artificiel. Les applications sont multiples, y compris dans le monde post-quantique. Dans la lignée de notre partage sur les entiers, nous proposons un schéma cryptographique de mise en gage basé sur des problèmes de sac-à-dos modulaire. En particulier, il permet des arguments efficaces pour la satisfiabilité de circuits génériques. Ensuite, nous présentons une construction de preuve utilisant la conversion entre les partages de secrets additifs et multiplicatifs, conduisant à des preuves efficaces de relations linéaires et multiplicatives. Les applications sont encore une fois multiples lors de la conception d'arguments et de signatures numériques. Enfin, laissant de côté la conception de protocoles, nous explorons les fondements de la cryptographie avec des preuves à divulgation nulle de connaissance avec prouveurs multiple, un cadre pour distribuer le travail du prouveur. Pour saisir tout l'intérêt de cette répartition, nous ajoutons à la littérature un résultat fondamental sur les preuves à seuil pour un langage NP générique.
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.
Concevoir des systèmes cryptographiques post-quantiques efficaces, pratiques et sûrs Cette thèse explore des stratégies d’optimisation pour la cryptographie post-quantique. Par systèmes cryptographiques post-quantiques, nous entendons des schémas classiques (non quantiques) dont la sécurité est destinée à résister à des attaques provenant d’ordinateurs quantiques.Premièrement, nous étudions des systèmes cryptographiques dans le cadre GPV avec des réseaux ou des codes non structurés qui souffrent généralement de clés de grande taille. Nous traitons ce problème avec une méthode permettant de remplacer les grandes clés publiques dans les signatures de type GPV par de plus petites clés de vérification privées. Cela réduit significativement le stockage et le temps d’exécution du vérificateur tout en préservant la sécurité. Appliquée aux schémas à signatures courtes Wave et Squirrels, notre méthode compresse les clés de Squirrels-I de 665 kB à 20{,}7 kB et les clés de Wave822 de 3{,}5 MB à 207{,}97 kB. Cela est particulièrement utile lorsque de nombreuses vérifications sont effectuées avec la même clé (par exemple, les mises à jour logicielles, les certificats racine). Deuxièmement, nous présentons quelques accélérations pour le calcul d’isogénies. L’une réorganise l’évaluation des formules de Vélu pour accélérer l’évaluation des ell-isogénies pour de nombreux nombres premiers ell, ce qui constitue un calcul de base dans de nombreux systèmes cryptographiques à base d’isogénies. Une autre vise les isogénies rationnelles dont les noyaux sont engendrés par des éléments irrationnels. Nos techniques accélèrent les schémas à base d’isogénies tels que CSIDH, CSI-FiSh et CRS.Enfin, nous proposons des algorithmes classiques de recherche parallèle de collisions pour les logarithmes discrets restreints multidimensionnels. La cryptographie basée sur les actions de groupes, et plus spécifiquement les emph{Restricted Effective Group Actions} (REGA), est profondément liée à ces problèmes. Une méthode existante pour résoudre les logarithmes discrets restreints multidimensionnels est l’algorithme de Gaudry--Schost. Cependant, il ne s’applique qu’à de faibles dimensions, ce qui ne correspond pas aux actions de groupes à base d’isogénies actuelles. Nous étendons l’algorithme de Gaudry--Schost à des dimensions plus élevées, offrant une vision plus approfondie des menaces classiques pour les échanges de clés REGA.
La cryptographie post-quantique est une branche de la cryptographie qui vise à concevoir des systèmes cryptographiques non quantiques (c'est-à-dire classiques), qui sont protégés contre un adversaire possédant un ordinateur quantique. Dans cette thèse, nous nous concentrons sur l'étude de deux problèmes fondamentaux pour la cryptographie post-quantique : le problème du plus court vecteur (SVP) et le problème de la somme de sous-ensembles aléatoires. Le SVP demande de trouver le plus court vecteur non nul d'un réseaux euclidien donné. Il sert de jauge pour quantifier la sécurité de la cryptographie reposant sur les réseaux euclidiens, qui est considérée comme prometteuse pour l'ère post-quantique. Les principales approches pour résoudre le SVP sont les algorithmes de tamisage, qui utilisent un temps et un espace exponentiels, et les algorithmes d'énumération, qui utilisent un temps superexponentiel et un espace polynomial. Dans cette thèse, nous donnons tout d'abord un compromis temps-mémoire prouvable qui interpole approximativement entre les garanties de ressources des algorithmes de tamisage et celles des algorithmes d'énumération. Nous montrons ensuite l'algorithme quantique prouvable le plus rapide connu qui résout le SVP en temps 2^(0.9535n) et en mémoire classique 2^(0.5n+o(n)) avec seulement un nombre poly(n) de qubits. Nous montrons également le meilleur algorithme prouvable classique connu dont la complexité en mémoire est de 2^(0.5n+o(n)). Quant aux algorithmes d'énumération, on pensait auparavant qu'ils pouvaient bénéficier d'une accélération quadratique quantique grâce à l'algorithme de Grover. Nous montrons que cette accélération quadratique peut effectivement être obtenue pour l'algorithme d'énumération de base et ses variantes d'élagage cylindrique et discret, mais avec des algorithmes quantiques plus sophistiqués tels que la marche quantique sur les arbres. Notre accélération quantique s'applique également à l'élagage extrême où l'on répète le processus d'énumération sur plusieurs bases réduites. Le problème de la somme de sous-ensembles aléatoires sous-tend également certains schémas cryptographiques visant à la sécurité post-quantique, bien qu'il soit principalement de nature académique. Dans un contexte de cryptanalyse, il sert souvent d'outil car de nombreux problèmes sur lesquels se fonde la cryptographie moderne peuvent être exprimés comme des variantes (vectorielles) du problème de la somme de sous-ensembles. Plus récemment, il a également été démontré qu'il peut être utilisé comme élément de base dans certains algorithmes de décalage caché quantique, qui ont des applications dans la cryptanalyse quantique de schémas symétriques et de schémas reposant sur les isogénies. Dans cette thèse, nous présentons de nouveaux algorithmes classiques et quantiques pour la résolution du problème de la somme de sous-ensembles aléatoires. Nous obtenons d'abord l'algorithme classique le plus rapide connu en temps Õ(2^0.283n)). Ensuite, nous améliorons l'état de l'art des algorithmes quantiques pour ce problème dans plusieurs directions. Nous concevons un algorithme avec un temps asymptotique Õ(2^0.236n), avec l'avantage d'utiliser une mémoire classique avec accès aléatoire quantique. Les algorithmes connus précédemment utilisaient des marches quantique, et nécessitaient une mémoire quantique avec accès aléatoire quantique.Nous proposons également des marches quantiques plus rapides pour ce problème en temps Õ(2^0.216n). Ce temps dépend d'une heuristique concernant le temps de mise à jour dans les marches quantiques. Les algorithmes précédents pour ce problème dépendaient eux aussi de cette heuristique. Nous montrons comment surmonter partiellement cette heuristique, et nous obtenons un algorithme quantique de temps Õ(2^0.218n) ne nécessitant que les heuristiques standard du problème de la somme de sous-ensembles aléatoires.