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.
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.
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é.
Dans la vie, on peut avoir besoin de communiquer avec des parties auxquelles on ne fait pas confiance, d'où l'importance de systèmes capables de contrôler ce type de communications. Des systèmes peuvent garantir, par exemple, un ballottage secret, des ventes aux enchères secrètes, des levées d'impôt tout en conservant l'intimité, l'authentification à distance à un ordinateur, l'aide anonyme de la police dans leurs enquêtes, etc. La cryptographie peut aider, au moins, dans quelques cas parmi ceux-ci, par la régularisation du flux d'information de telle manière qu'on n'aura plus besoin de faire confiance à l'autre partie. On fera confiance, seulement, aux systèmes cryptographiques utilisés. Une primitive, appelée mise en gage, est d'une importance suprême dans la cryptographie bipartite, où deux parties qui ne se font pas confiance essayent tout de même d'accomplir un calcul commun sur des données privées (calculer une fonction publique de leurs données secrètes). Cette primitive va être l'objet de ce mémoire. On va expliquer jusqu'à quel point on peut accomplir des taches cryptographiques de façon inconditionnellement sécuritaire, sous la seule hypothèse que la mécanique quantique et la relativité restreinte sont valides. Ce mémoire est largement basé sur les travaux de Mayers [52,53,54,55], Lo et Chau [49,50], Brassard, Crépeau, Mayers et Salvail [15], Spekkens et Rudolph [73], Hardy et Kent [35], Ishizaka [39] et Kent [43,44]. Il fait à la fois une présentation de la cryptographie quantique et une synthèse des travaux essentiels concernant les protocoles de mise en gage quantiques et relativistes. Nous allons donc commencer par une introduction sur l'histoire de la cryptographie \nclassique et son prolongement naturel à ses homologues, quantique et relativiste, qui permettent d'obtenir de meilleurs résultats. Ensuite, nous introduirons un certain nombre \nd'outils mathématiques utiles à la description de la cryptographie quantique. Nous y présenterons également les preuves de plusieurs résultats à la base de la cryptographie quantique, tels que la décomposition de Schmidt, la purification, le théorème GHJW, le théorème d'Ulmann, le théorème de non-clonage, le théorème de la représentation de Kraus, etc. Nous discuterons aussi des concepts de base de l'informatique quantique, comme la mesure projective et généralisée, l'évolution des systèmes quantiques non isolés, la trace partielle, l'opérateur de densité, etc. Nous aborderons le protocole de la mise en gage proprement dit en exposant en détail la preuve du théorème de l'impossibilité de Mayers, Lo et Chau. Nous y présentons également le travail de Rudolph et Spekkens qui ont calculé les degrés optimaux de lien et de camouflage qui peuvent être obtenus simultanément dans tout protocole de mise en gage quantique non relativiste. Il s'agit-là d'une caractéristique qu'aucun protocole classique non relativiste ne peut assurer. Un autre type de sécurité pour ce protocole est étudié aussi, c'est celui de la mise en gage sensible à la tricherie "cheat sensitive" pour lequel on croyait que le protocole quantique de Hardy et Kent fonctionnait alors que lshizaka a démontré récemment que ce n'est pas le cas. Pire, il a même remis en question toute possibilité de réaliser ce type de sécurité en ce basant sur l'utilisation du protocole du tir à pile ou face comme sous-protocole. La cryptographie relativiste fera l'objet de notre dernier chapitre. Nous commencerons par montrer comment la théorie de la relativité restreinte, et donc l'impossibilité qu'un signal puisse se déplacer à une vitesse supérieur à celle de la lumière, peut être exploitée pour construire un protocole de mise en gage temporairement sécuritaire, c'est celui de Brassard, Crépeau, Mayers et Salvail. Nous présenterons ensuite le premier protocole relativiste d'une mise en gage continuellement sécuritaire, celui de Kent, et la preuve de sa sécurité. Ce protocole ne peut malheureusement pas être implémenté, même s'il est théoriquement sûr. Nous terminerons cette étude par une description d'un deuxième protocole relativiste du même auteur, qui va remédier aux problèmes liés à l'impossibilité pratique du premier protocole. Les preuves de la sécurité de ce dernier contre les attaques classiques et quantiques du type Mayers, Lo et Chau vont être abordées. ______________________________________________________________________________ MOTS-CLÉS DE L’AUTEUR : Informatique quantique, Mise en gage quantique, Mise en gage quantique sensible à la tricherie, Mise en gage relativiste.
Pile-ou-face et mise-en-gage de bit quantique : bornes optimales, constructions pratiques et sécurité calculatoire L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques.
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.
L'avènement de l'informatique quantique permet de réétudier les primitives cryptographiques avec une sécurité inconditionnelle, c'est à dire sécurisé même contre des adversaires tout puissants. En 1984, Bennett et Brassard ont construit un protocole quantique de distribution de clé. Dans ce protocole, deux joueurs Alice et Bob coopèrent pour partager une clé secrète inconnue d'une tierce personne Eve. Ce protocole a une sécurité inconditionnelle et n'a pasd'équivalent classique.Dans ma thèse, j'ai étudié les primitives cryptographiques à deux joueurs où ces joueurs ne se font pas confiance. J'étudie principalement le pile ou face quantique et la mise-en-gage quantique de bit. En informatique classique, ces primitivessont réalisables uniquement avec des hypothèses calculatoires, c'est-à-dire en supposant la difficulté d'un problème donné. Des protocoles quantiques ont été construits pour ces primitives où un adversaire peut tricher avec une probabilité constante strictement inférieure à 1, ce qui reste impossible classiquement. Néanmoins, Lo et Chau ont montré l'impossibilité de créer ces primitives parfaitement même en utilisant l'informatique quantique. Il reste donc à déterminer quelles sont les limites physiques de ces primitives.Dans une première partie, je construis un protocole quantique de pile ou face où chaque joueur peut tricher avec probabilité au plus 1/racine(2) + eps pour tout eps > 0. Ce résultat complète un résultat de Kitaev qui dit que dans un jeu de pile ou face quantique, un joueur peut toujours tricher avec probabilité au moins 1/racine(2). J'ai également construit un protocole de mise-en-gage de bit quantique optimal où un joueur peut tricher avec probabilité au plus 0,739 + eps pour tout eps > 0 puis ai montré que ce protocole est en fait optimal. Finalement, j'ai dérivé des bornes inférieures et supérieures pour une autre primitive: la transmission inconsciente, qui est une primitive universelle.Dans une deuxième partie, j'intègre certains aspects pratiques dans ces protocoles. Parfois les appareils de mesure ne donnent aucun résultat, ce sont les pertes dans la mesure. Je construis un protocole de lancer de pièce quantique tolérant aux pertes avec une probabilité de tricher de 0,859. Ensuite, j'étudie le modèle dispositif-indépendant où on ne suppose plus rien sur les appareils de mesure et de création d'état quantique.Finalement, dans une troisième partie, j'étudie ces primitives cryptographiques avec un sécurité computationnelle. En particulier, je fais le lien entre la mise en gage de bit quantique et les protocoles zero-knowledge quantiques.