Dodging impossibilities in quantum cryptography : on the feasibility of one-time programs, signing quantum states, and cryptography without one-way functions
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.
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.
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é.
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é.
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
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.
La cryptographie quantique a été largement définie comme une forme novatrice de cryptographie ne reposant sur aucune hypothèse de difficulté computationnelle. Cependant, avec l'évolution du domaine, et en particulier alors que la distribution quantique de clé (QKD) atteint des niveaux élevés de préparation technologique, il semble qu'il faille trouver un équilibre critique. D'une part, il y a la quête du niveau de sécurité théorique le plus élevé. D'autre part, une seconde direction consiste à optimiser la sécurité et la performance pour une utilisation réelle, tout en offrant un avantage par rapport à la cryptographie classique. Dans cette thèse, nous avons exploré de nouvelles voies vers cette seconde direction, à savoir la cryptographie quantique en conditions réelles.Dans le premier projet, nous défendons un message simple mais puissant : les attaques les plus dangereuses contre la QKD, pour lesquelles le développement de contre-mesures est crucial, sont les plus faciles à mettre en œuvre. Par conséquent, nous effectuons une évaluation de la vulnérabilité d'un dispositif de QKD à variables continues, proposant une nouvelle méthodologie pour la certification de sécurité basée sur le classement des attaques.Dans le deuxième projet, nous introduisons une construction explicite pour un protocole de distribution de clés dans le modèle de sécurité Quantum Computational Timelock (QCT), où l'on suppose que le chiffrement sécurisé computationnellement ne peut être rompu qu'après un temps bien plus long que le temps de cohérence des mémoires quantiques disponibles. En tirant parti des hypothèses QCT, nous construisons un protocole de distribution de clés basé sur le problème de Hidden Matching, pour lequel il existe un écart exponentiel en complexité de communication unidirectionnelle entre les stratégies classiques et quantiques. En particulier, en exploitant cet écart exponentiel, nous débloquons la possibilité d'envoyer plusieurs copies du même état pour réaliser un établissement de clé sécurisé à long terme avec des performances qui vont au-delà de la QKD standard.En nous appuyant sur notre travail théorique sur l'établissement de clés, dont la sécurité et l'efficacité reposent sur la capacité des deux parties à résoudre un problème de complexité de communication quantique plus efficacement que ce qui est possible classiquement, dans le dernier projet expérimental, nous étudions la faisabilité de démontrer un avantage quantique en complexité de communication. En particulier, nous exploitons le mélange de modes complexe inhérent aux fibres multimodes en employant des techniques de wavefront shaping pour aborder les problèmes de complexité de communication quantique.