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.
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.
Protocoles de chiffrement quantiques de plusieurs parties en environnements réalistes Cette thèse se situe à l’interface entre la théorie quantique et les expériences, en mettant l’accent sur les protocoles pratiques qui peuvent être mises en place en utilisant la technologie présente. Notre objectif est de contribuer à la construction d’un cadre général pour la conception et la mise en oeuvre de schémas de chiffrement quantiques qui permettront d’améliorer la sécurité des futurs réseaux de télécommunication. En outre, cette thèse veut avancer la recherche pertinente sur la physique quantique et l’informatique, en améliorant notre compréhension du phénomène d’intrication. Les corrélations des états intriqués ne peuvent pas être reproduites par des moyens classiques, ce qui permet d’effectuer des tâches (par exemple la téléportation et le codage super-dense) qui sont autrement impossibles. Il est donc d’une importance majeure d’être capables de vérifier si un état quantique est intriqué. Dans cette thèse, nous montrons comment vérifier efficacement si une source physique peut créer des états intriqués multipartites et les partager avec de nombreuses parties, dont certains sont malhonnêtes et collaborent avec la source. Ce protocole pourrait s’avérer essentiel pour tout type de calcul quantique entre les parties méfiantes et pourrait aussi faciliter la délégation sécurisée des tâches de calcul aux serveurs quantiques puissants qui ne sont pas fiables. Finalement, nous étudions le lien entre la théorie des jeux et la non-localité quantique, dans le cadre de jeux bayésiens. Nous examinons comment l’intrication partagé aide les joueurs gagner un jeu avec une probabilité plus élevée que les ressources classiques pourraient atteindre.
Sécurité étendue de la cryptographie fondée sur les réseaux Euclidiens La cryptographie fondée sur les réseaux euclidiens représente une alternative prometteuse à la cryptographie asymétrique utilisée actuellement, en raison de sa résistance présumée à un ordinateur quantique universel. Cette nouvelle famille de schémas asymétriques dispose de plusieurs atouts parmi lesquels de fortes garanties théoriques de sécurité, un large choix de primitives et, pour certains de ses représentants, des performances comparables aux standards actuels. Une campagne de standardisation post-quantique organisée par le NIST est en cours et plusieurs schémas utilisant des réseaux euclidiens font partie des favoris. La communauté scientifique a été encouragée à les analyser car ils pourraient à l'avenir être implantés dans tous nos systèmes. L'objectif de cette thèse est de contribuer à cet effort. Nous étudions la sécurité de ces nouveaux cryptosystèmes non seulement au sens de leur résistance à la cryptanalyse en ''boîte noire'' à l'aide de moyens de calcul classiques, mais aussi selon un spectre plus large de modèles de sécurité, comme les attaques quantiques, les attaques supposant des failles d'utilisation, ou encore les attaques par canaux auxiliaires. Ces différents types d’attaques ont déjà été largement formalisés et étudiés par le passé pour des schémas asymétriques et symétriques pré-quantiques. Dans ce mémoire, nous analysons leur application aux nouvelles structures induites par les réseaux euclidiens. Notre travail est divisé en deux parties complémentaires : les contremesures et les attaques. La première partie regroupe nos contributions à l'effort actuel de conception de nouvelles protections algorithmiques afin de répondre aux nombreuses publications récentes d’attaques par canaux auxiliaires. Les travaux réalisés en équipe auxquels nous avons pris part on abouti à l'introduction de nouveaux outils mathématiques pour construire des contre-mesures algorithmiques, appuyées sur des preuves formelles, qui permettent de prévenir systématiquement les attaques physiques et par analyse de temps d'exécution. Nous avons ainsi participé à la protection de plusieurs schémas de signature fondés sur les réseaux euclidiens comme GLP, BLISS, qTesla ou encore Falcon. Dans une seconde partie consacrée à la cryptanalyse, nous étudions dans un premier temps de nouvelles attaques qui tirent parti du fait que certains schémas de chiffrement à clé publique ou d'établissement de clé peuvent échouer avec une faible probabilité. Ces échecs sont effectivement faiblement corrélés au secret. Notre travail a permis d’exhiber des attaques dites « par échec de déchiffrement » dans des modèles de failles d'utilisation ou des modèles quantiques. Nous avons d'autre part introduit un outil algorithmique de cryptanalyse permettant d’estimer la sécurité du problème mathématique sous-jacent lorsqu’une information partielle sur le secret est donnée. Cet outil s’est avéré utile pour automatiser et améliorer plusieurs attaques connues comme des attaques par échec de déchiffrement, des attaques classiques ou encore des attaques par canaux auxiliaires.
Towards unclonable cryptography in the plain model La mécanique quantique génère de nouvelles menaces pour la cryptographie, mais elle offre également de nouveaux outils pour construire des primitives cryptographiques qui ne peuvent être réalisées dans le monde classique. Parmi ces primitives figurent les primitives inclonables, qui exploitent le théorème de non-clonage des états quantiques : la propriété surprenante qu’ils ne peuvent être copiés. Dans la première partie de cette thèse, nous donnons un aperçu approfondi des primitives inclonables, et en particulier de trois primitives principales : la quantum money, fournissant des jetons vérifiables inclonables; l’unclonable encrytion, un schéma de chiffrement avec chiffrés inclonables; et enfin la copy-protection, dans laquelle un vendeur envoie des programmes inclonables à ses clients. Nous définissons chacune de ces primitives, discutons de leur historique, et donnons des exemples de constructions. Dans la seconde partie, nous nous concentrons sur la copy-protection et l’unclonable encryption. Bien que ces primitives aient reçu beaucoup d’attention ces dernières années, elles ne sont pas encore entièrement comprises. En particulier, décider si elles existent dans le plain model (dans lequel nous ne pouvons pas utiliser d’oracles aléatoires (quantiques)) reste une question ouverte. Nous progressons vers cet objectif en présentant de nouvelles constructions pour ces primitives, avec une sécurité dans le plain model, en supposant de nouvelles conjectures. Pour prouver la sécurité de nos constructions, nous définissons et prouvons une nouvelle propriété dit de “monogamie” des coset states — sans doute les états quantiques les plus utiles lorsqu’il s’agit de construire des primitives inclonables. Nous pensons que cette nouvelle propriété est d’un intérêt indépendant. Comme contributions indépendantes, nous définissons deux nouvelles propriétés de sécurité pour une autre primitive inclonable, les tokenized signatures, et présentons une construction satisfaisant ces nouvelles propriétés. Les preuves de sécurité découlent de notre nouvelle propriété de “monogamie”, ainsi que d’une variante d’une des propriétés principales des coset states, que nous définissons et prouvons. Les protocoles cryptographiques inclonables nécessitent souvent une puissance quantique importante pour toutes les parties impliquées. Comme un tel modèle est peu susceptible d’être réalisable dans un avenir proche, nous examinons dans une troisième partie la cryptographie inclonable semi-quantique, dans laquelle des utilisateurs classiques interagissent avec un serveur quantique puissant. La plupart des primitives inclonables sont basées sur les coset states, nous construisons donc un protocole de préparation à distance de ces états, dans lequel un utilisateur classique fournit des instructions au serveur quantique sur la manière de construire coset states. De plus, cette préparation est effectuée de manière aveugle, dans le sens où le serveur n’a pas d’information sur les coset states qu’il a préparés. Cela nous permet d’utiliser ce protocole pour construire des primitives inclonables de manière semi-quantique.