Fonctions Pseudo-aléatoires Contraintes : nouvelles constructions et liens avec le calcul sécurisé Les fonctions pseudo-aléatoires (Pseudorandom Functions, alias PRFs) ont été introduites en 1986, par Goldreich, Goldwasser et Micali, comme moyen efficace de générer de l’aléa et servent depuis d’outils essentiels en cryptographie. Ces fonctions utilisent une clé secrète principale pour faire correspondre différentes entrées à des sorties pseudo-aléatoires. Les fonctions pseudo-aléatoires contraintes (Constrained Pseudorandom Functions, alias CPRFs), introduites en 2013, étendent les PRFs enautorisant la délégation des clés contraintes qui permettent l’évaluation de la fonction uniquement sur des sous-ensembles spécifiques d’entrées. Notamment, même avec cette évaluation partielle, la sortie d’une CPRF devrait rester pseudo-aléatoire sur les entrées en dehors de ces sous-ensembles. Dans cette thèse, nous établissons des liens entre les CPRFs et deux autres outils cryptographiques qui ont été introduits dans le contexte du calcul sécurisé : 1. Nous montrons comment les CPRFs peuvent être construites à partir de protocoles de partage de secrets homomorphes (Homomorphic Secret Sharing, alias HSS). Les protocoles de partage de secrets homomorphes permettent des calculs distribués sur des parties d’un secret. Nous commençons par identier deux nouvelles versions des protocoles HSS et montrons comment elles peuvent être transformées en CPRFs générant des clés contraintes pour des sous-ensembles d’entrées qui peuvent être exprimés via des prédicats de produit scalaire ou de NC1. Ensuite, nous observons que les constructions de protocoles HSS qui existent déjà dans la littérature peuvent être adaptées à ces nouvelles extensions. Cela conduit à la découverte de cinq nouvelles constructions CPRF basées sur diverses hypothèses de sécurité standardes. 2. Nous montrons comment les CPRFs peuvent être utilisées pour construire des fonctions de corrélation pseudo-aléatoires (Pseudorandom Correlation Functions, alias PCFs) pour les corrélations de transfert inconscient (Oblivious Transfer, alias OT). Les PCFs pour les corrélations OT permettent à deux parties de générer des paires corrélées OT qui peuvent être utilisées dans des protocoles de calcul sécurisés rapides. Ensuite, nous détaillons l’instanciation de notre transformation en appliquant une légère modification à la construction PRF bien connue de Naor et Reingold. Enfin, nous présentons une méthode de génération non-interactive de clés d’évaluation pour cette dernière instanciation, qui permet d’obtenir une PCF à clé publique efficace pour les corrélations OT à partir d’hypothèses standardes.
Fonctions Pseudo-aléatoires Contraintes : nouvelles constructions et liens avec le calcul sécurisé Les fonctions pseudo-aléatoires (Pseudorandom Functions, alias PRFs) ont été introduites en 1986, par Goldreich, Goldwasser et Micali, comme moyen efficace de générer de l’aléa et servent depuis d’outils essentiels en cryptographie. Ces fonctions utilisent une clé secrète principale pour faire correspondre différentes entrées à des sorties pseudo-aléatoires. Les fonctions pseudo-aléatoires contraintes (Constrained Pseudorandom Functions, alias CPRFs), introduites en 2013, étendent les PRFs enautorisant la délégation des clés contraintes qui permettent l’évaluation de la fonction uniquement sur des sous-ensembles spécifiques d’entrées. Notamment, même avec cette évaluation partielle, la sortie d’une CPRF devrait rester pseudo-aléatoire sur les entrées en dehors de ces sous-ensembles. Dans cette thèse, nous établissons des liens entre les CPRFs et deux autres outils cryptographiques qui ont été introduits dans le contexte du calcul sécurisé : 1. Nous montrons comment les CPRFs peuvent être construites à partir de protocoles de partage de secrets homomorphes (Homomorphic Secret Sharing, alias HSS). Les protocoles de partage de secrets homomorphes permettent des calculs distribués sur des parties d’un secret. Nous commençons par identier deux nouvelles versions des protocoles HSS et montrons comment elles peuvent être transformées en CPRFs générant des clés contraintes pour des sous-ensembles d’entrées qui peuvent être exprimés via des prédicats de produit scalaire ou de NC1. Ensuite, nous observons que les constructions de protocoles HSS qui existent déjà dans la littérature peuvent être adaptées à ces nouvelles extensions. Cela conduit à la découverte de cinq nouvelles constructions CPRF basées sur diverses hypothèses de sécurité standardes. 2. Nous montrons comment les CPRFs peuvent être utilisées pour construire des fonctions de corrélation pseudo-aléatoires (Pseudorandom Correlation Functions, alias PCFs) pour les corrélations de transfert inconscient (Oblivious Transfer, alias OT). Les PCFs pour les corrélations OT permettent à deux parties de générer des paires corrélées OT qui peuvent être utilisées dans des protocoles de calcul sécurisés rapides. Ensuite, nous détaillons l’instanciation de notre transformation en appliquant une légère modification à la construction PRF bien connue de Naor et Reingold. Enfin, nous présentons une méthode de génération non-interactive de clés d’évaluation pour cette dernière instanciation, qui permet d’obtenir une PCF à clé publique efficace pour les corrélations OT à partir d’hypothèses standardes.
Calcul sécurisé efficace à partir de pseudo-aléa corrélé Dans cette thèse, nous explorons les avancées en calcul multipartite sécurisé (MPC), permettant à plusieurs parties de calculer conjointement des fonctions arbitraires tout en préservant la confidentialité de leurs entrées. Notre étude se concentre sur le MPC avec aléa corrélé, où l'efficacité est améliorée grâce à des corrélations générées en phase de prétraitement. Nous examinons deux paradigmes clés pour générer ces corrélations: les Générateurs de Corrélations Pseudoaléatoires (PCGs) et les Fonctions de Corrélations Pseudoaléatoires (PCFs). Tout d'abord, nous proposons de nouvelles constructions de PCG pour l'Intersection Privée d'Ensembles (PSI), offrant une sécurité renforcée ou de meilleures performances. Nous explorons ensuite les applications des PCGs et PCFs aux preuves à divulgation nulle de connaissance (ZKPs), en couvrant à la fois les cadres interactifs et non interactifs. Pour les ZKPs interactives, nous concevons un protocole vérifiable de manière privée pour la satisfaisabilité de circuits, avec une communication sous-linéaire et un calcul efficace. Dans le cadre non interactif, nous introduisons une nouvelle preuve à divulgation nulle de connaissance pour vérificateur désigné (DV-NIZK) exploitant les PCF avec une structure à clé publique (PK-PCF). Enfin, nous introduisons un nouveau cadre MPC pour les circuits binaires, basé sur un PCG optimisé pour les petits corps finis.
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é.
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.
Primitives cryptographiques dans des modèles idéalisés quantiques 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é.
Protocoles avec Sécurité Inconditionnelle issus de Techniques de la Théorie des Codes Le sujet de cette thèse est la cryptographie et son interconnexions avec la théorie des codes. En particulier, on utilise des techniques issues de la théorie des codes pour construire et analyser des protocoles cryptographiques avec des propriétés nouvelles ou plus avancées. On se concentre d'abord sur le partage de secret ou secret sharing, un sujet important avec de nombreuses applications pour la Cryptographie actuelle. Dans la variante à laquelle on s'intéresse, un schéma de partage de secret reçoit en entrée un élément secret, et renvoie en sortie n parts de telle façon que chaque ensemble de parts de taille suffisamment petite ne donne aucune information sur le secret (confidentialité), tandis que chaque ensemble de taille suffisamment grande permet de reconstituer le secret (reconstruction). Un schéma de partage de secret peut donc être vu comme une solution à un problème de communication où un émetteur Alice est connectée avec un destinataire Bob par n canaux distincts, dont certains sont contrôlés par un adversaire Ève. Alice peut utiliser un schéma de partage de secret pour communiquer un message secret a Bob de telle façon qu'Ève n'apprenne aucune information sur le secret en lisant les données transmises sur les canaux qu'elle contrôle, tandis que Bob peut recevoir le message même si Ève bloque ces dits canaux. Notre contributions au partage de secret concernent ses liens avec la théorie des codes ; comme les deux domaines partagent un même but (récupérer des données à partir d'informations partielles), ce n'est pas surprenant qu'ils aient connu une interaction longue et fertile. Plus précisément, Massey commença une analyse fructueuse à propos de la construction et de l'étude d'un schéma de partage de secret à partir d'un code correcteur. L'inconvénient de cette analyse est que la confidentialité d'un schéma de partage de secret est estimé grâce au dual du code sous-jacent ; cela peut être problématique vu qu'il pourrait ne pas être possible d'obtenir des codes avec des propriétés souhaitables qui aient aussi un bon code dual. On contourne ce problème en établissant une connexion nouvelle entre les deux domaines, telle que la confidentialité d'un schéma de partage de secrets n'est plus contrôlée par le dual du code sous-jacent. Cela nous permet d'exploiter complètement le potentiel de certaines constructions récentes de codes pour obtenir des meilleurs schémas; on illustre ceci avec deux applications. Premièrement, en utilisant des codes avec codage et décodage en temps linéaire on obtient une famille de schémas de partage de secret où le partage (calcul des parts issues du secret) tout comme la reconstruction peuvent s'effectuer en temps linéaire ; pour des seuils de confidentialité et de reconstruction croissants, ceci restait jusqu'à présent un problème ouvert. Deuxièmement, on utilise des codes avec décodage en liste pour construire des schémas de partage de secret robustes, c'est-à-dire des schémas qui peuvent reconstituer le secret même si certaines parts sont incorrectes, sauf avec une petite probabilité d'erreur. etc...
Depuis l'apparition de la cryptographie moderne, le calcul sécurisé (MPC) a longuement été étudié. Le MPC permet à un groupe de parties (ou joueurs) d'effectuer ensemble un ou plusieurs calculs sur des données secrètes, tout en garantissant que les joueurs n'obtiennent rien de plus que le résultat et ce qui peut en être déduit. Le développement massif de notre utilisation quotidienne d'Internet rend le besoin de méthodes de calcul sécurisé plus urgent que jamais : les calculs sur des données privées sont omniprésents, des algorithmes de recommandation aux enchères électroniques. Les algorithmes de MPC modernes bénéficient grandement de l'apport d'aléa corrélé, afin d'obtenir des protocoles rapides. Cet aléa corrélé doit être généré massivement au préalable pour que les protocoles de MPC puissent être efficaces. Toutefois, réaliser cette génération d'aléa corrélé efficacement reste encore un défi. Dans cette thèse, nous étudions les Générateurs de Corrélations Pseudo-aléatoires (PCGs). Cette primitive cryptographique transforme une petite quantité d'aléa corrélé en une large quantité de pseudo-aléa corrélé, tout en étant efficace en ce qui concerne le temps de calcul et la communication. Nous présentons différentes constructions de PCG dont la sécurité repose sur des variantes de l'hypothèse de Décodage de Syndrome (SD), une hypothèse classique en théorie des codes. L'intuition derrière les constructions proposées est de mélanger l'hypothèse SD avec certaines techniques de MPC qui permettent de partager de manière additive des vecteurs creux. Nos résultats obtenus battent l'état de l'art en ce qui concerne les protocoles de calcul sécurisé nécessitant plus de deux joueurs lorsque le calcul est effectué sur un corps fini de taille > 2. Nous montrons également comment supprimer cette contrainte au prix d'un léger surcoût en communication. Nous considérons également la construction de Fonctions Pseudo-aléatoires Corrélées (PCFs). Les PCFs produisent des corrélations à la volée : les joueurs détiennent chacun des fonctions corrélées de sorte que les sorties des fonctions, lorsqu'elles sont évaluées sur la même entrée, soient corrélées. Ces objets offrent plus de flexibilité que les PCGs, mais sont aussi plus difficiles à construire. Nous nous appuyons à nouveau sur des variantes de SD pour construire des PCFs. Nous nous basons sur une construction de PCF déjà établie, montrant que la preuve de sécurité associée était incorrecte, et proposons une correction. De plus, nous présentons des optimisations de la construction, provenant d'une meilleure analyse et d'un calcul précis des paramètres nécessaires via des simulations. Nous obtenons des paramètres utilisables en pratique. Cette thèse repose majoritairement sur l'hypothèse SD. La recherche d'une bonne complexité implique des efforts pour trouver les codes les plus efficaces tout en garantissant que la sécurité ne soit pas compromise. Nous considérons un modèle permettant l'étude de l'efficacité des attaques prometteuses contre SD et ses variantes. Pour chaque construction mentionnée précédemment, nous menons une analyse de sécurité approfondie de la variante associée de SD et tentons d'attaquer notre propre schéma pour calculer des paramètres concrets.