Ce memoire examine le rôle des fonctions à sens unique en cryptographie quantique. À cette fin, elle se penche sur les générateurs d’états quantiques pseudaléatoires, un concept récemment introduit par Ji, Liu et Song, qui sont analogues aux générateurs pseudaléatoires. Des travaux récents ont montré que ces générateurs peuvent être construits à partir de toute fonction à sens unique (sécurisée quantiquement) et peuvent être utilisés pour créer diverses primitives cryptographiques quantiques, telles que l’engagement de bit quantique, le chiffrement quantique à clé symétrique et les codes d’authentification de messages quantiques. Cela implique que, tout comme en cryptographie classique, les fonctions à sens unique constituent une condition suffisante pour réaliser la cryptographie quantique.Bien qu’elles soient suffisantes, elles ne sont peut-être pas strictement nécessaires. Des travaux novateurs, présentés par Kretschmer, ont montré qu’il existe certains mondes relativisés dans lesquels des générateurs d’états quantiques pseudaléatoires existent alors même que les fonctions à sens unique n’existent pas. Cela suggère que les générateurs d’états quantiques pseudaléatoires pourraient reposer sur des hypothèses plus faibles. Ainsi, même si la cryptographie classique s’avérait impossible, la cryptographie quantique ne le serait peut-être pas. Ce memoire présente un résumé complet de ces résultats, en mettant l’accent sur la clarté et la lisibilité, et discute des perspectives de recherche prometteuses
Ce memoire examine le rôle des fonctions à sens unique en cryptographie quantique. À cette fin, elle se penche sur les générateurs d’états quantiques pseudaléatoires, un concept récemment introduit par Ji, Liu et Song, qui sont analogues aux générateurs pseudaléatoires. Des travaux récents ont montré que ces générateurs peuvent être construits à partir de toute fonction à sens unique (sécurisée quantiquement) et peuvent être utilisés pour créer diverses primitives cryptographiques quantiques, telles que l’engagement de bit quantique, le chiffrement quantique à clé symétrique et les codes d’authentification de messages quantiques. Cela implique que, tout comme en cryptographie classique, les fonctions à sens unique constituent une condition suffisante pour réaliser la cryptographie quantique.Bien qu’elles soient suffisantes, elles ne sont peut-être pas strictement nécessaires. Des travaux novateurs, présentés par Kretschmer, ont montré qu’il existe certains mondes relativisés dans lesquels des générateurs d’états quantiques pseudaléatoires existent alors même que les fonctions à sens unique n’existent pas. Cela suggère que les générateurs d’états quantiques pseudaléatoires pourraient reposer sur des hypothèses plus faibles. Ainsi, même si la cryptographie classique s’avérait impossible, la cryptographie quantique ne le serait peut-être pas. Ce memoire présente un résumé complet de ces résultats, en mettant l’accent sur la clarté et la lisibilité, et discute des perspectives de recherche prometteuses
Cette thèse par articles étudie les frontières de la faisabilité cryptographique quantique, en démontrant comment les propriétés singulières de l’information quantique peuvent être exploitées pour contourner des résultats d’impossibilité fondamentaux. Nous explorons trois régimes distincts dans lesquels des théorèmes d’impossibilité (≪ No-Go ≫) traditionnels sont surmontés : la réalisation de programmes à usage unique dans un modèle où la mémoire quantique de l’adversaire est de taille bornée, la signature de messages quantiques au moyen de contraintes temporelles et la réalisation de primitives cryptographiques sans avoir à supposer l’existence de fonctions à sens unique. La première partie de ce travail exploite le modèle de mémoire quantique bornée (Bounded Quantum Storage Model ), dans lequel les adversaires sont limités quant à leur mémoire quantique. Nous démontrons que cette limitation physique permet la construction de programmes à usage unique — une forme puissante d’obfuscation de programmes dont l’impossibilité est prouvée dans le modèle standard. De manière cruciale, puisque la sécurité découle de contraintes de mémoire plutôt que de difficulté calculatoire, nos constructions atteignent une sécurité au sens de la théorie de l’information. Nous utilisons les programmes à usage unique pour développer, pour la première fois, des applications cryptographiques fondamentales, notamment le chiffrement à clé asymétrique et les signatures numériques assortis de garanties au sens de la théorie de l’information. La deuxième contribution remet en question le paradigme établi de longue date selon lequel la signature de messages quantiques est intrinsèquement impossible. Nous introduisons les signatures dépendantes du temps, dont la sécurité est assurée par la synchronisation temporelle des processus de signature et de vérification. Nous montrons que ce cadre permet la signature d’états quantiques à l’aide de n’importe quelle fonction à sens unique et puzzle à verrou temporel (time-lock puzzle). De plus, nous démontrons qu’en recourant à des clés de vérification dynamiques qui évoluent au cours du temps, l’exigence de puzzles à verrou temporel peut être éliminée. Nous appliquons le schéma de signature à la construction du chiffrement à clé publique quantique authentifié dépendant du temps et de la monnaie quantique à clé publique. La dernière partie de la thèse contribue au corpus croissant de recherches réévaluant la nécessité fondamentale des fonctions à sens unique (OWF) en tant qu’hypothèse inimale pour une cryptographie non triviale. Plus précisément, nous fournissons une séparation en boîte noire démontrant qu’un générateur pseudo-aléatoire (PRG) augmenté d’une procédure d’échantillonnage d’entrée quantique représente une hypothèse potentiellement plus faible qu’un PRG traditionnel à échantillonnage uniforme, lequel est équivalent aux OWF. À partir de cette observation, nous montrons que des applications importantes, telles que l’authentification de messages et les mises en gage (commitments) avec communication classique, sont également séparées en boîte noire des PRG traditionnels. Cela apporte des éléments en faveur d’une nouvelle hypothèse, potentiellement plus faible, pour ces applications cryptographiques. Prises ensemble, ces contributions offrent une perspective différente des paysages dans lequel le cryptographie quantique peut-être développée. En remplaçant les hypothèses fondamentales — de la difficulté calculatoire vers des bornes de mémoire, de l’indépendance temporelle vers la dépendance temporelle, et de l’échantillonnage uniforme vers l’échantillonnage quantique — cette thèse établit qu’une gamme plus large de primitives sûres est faisable dans des modèles réalistes que ce qui est possible dans le modèle calculatoire standard.
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é.
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 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.
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.
Nous proposons l'étude des schémas de mise en gage post-quantiques de bit dont le camouflage est garanti au sens statistique, appelé mise en gage camouflante. Nous cherchons à établir l'hypothèse de calcul la plus faible qui garantit alors son caractère liant. Dans le monde classique, l'existence de fonctions à sens unique est nécessaire et suffisante pour y parvenir. Cependant au moment d'écrire ces lignes, l'hypothèse post-quantique la plus faible connue demande l'existence de fonctions de hachage à effondrement (collapsing hash functions). Cette hypothèse est plus forte que l’existence de fonctions à sens unique en ce sens qu'aucune réduction du type boîte noire ne peut transformer une fonction à sens unique en fonctions de hachage à effondrement. Le hachage interactif est une primitive introduite par Naor, Ostrovsky, Ventkatessen et Yung en 1998 [26] pour obtenir des mises en gage camouflantes à partir de n'importe quelle permutation à sens unique. Il s'agissait de la première étape d'une séquence de réductions qui permettent d'obtenir une mise en gage camouflante à partir de n'importe quelle fonction à sens unique, l'hypothèse la plus faible pour cette tâche. Le hachage interactif n'a toujours pas été montré sûr dans le monde post-quantique. Nous proposons une preuve presque complète qui une fois terminée permettrait de montrer qu’il est possible d'obtenir une mise en gage camouflante post-quantique à partir de n'importe quelle permutation à sens unique. L'existence de permutations à sens unique est une hypothèse post-quantique plus faible que l'existence de fonctions de hachage à effondrement. La preuve de sécurité du hachage interactif dans le monde classique utilise lourdement une technique difficile à appliquer dans le monde quantique: le rembobinage de l'adversaire. Nous comptons utiliser un résultat récent de Chiesa, Ma, Spooner et Zhandry [10] pour éviter certains problèmes dus au rembobinage des adversaires quantiques. Nous disons que la preuve est presque complète puisqu'il manque un dernier résultat qui ne semble pas être impossible à prouver dans un futur proche.