Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM.
Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire multiplicative" est plus forte que la méthode additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM.
Interaction à deux joueurs en informatique quantique : primitives cryptographiques et complexité en requêtes Cette thèse étudie deux aspects d'interaction entre deux joueurs dans le modèle du calcul et de la communication quantique.Premièrement, elle étudie deux primitives cryptographiques quantiques, des briques de base pour construire des protocoles cryptographiques complexes entre deux joueurs, comme par exemple un protocole d'identification. La première primitive est la ``mise en gage quantique". Cette primitive ne peut pas être réalisée de manière inconditionnellement sûre, mais il possible d'avoir une sécurité lorsque les deux parties sont soumis à certaines contraintes additionnelles. Nous étudions cette primitive dans le cas où les deux joueurs sont limités à l'utilisation d'états et d'opération gaussiennes, un sous-ensemble de la physique quantique central en optique, donc parfaitement adapté pour la communication via fibres optiques. Nous montrons que cette restriction ne permet malheureusement pas la réalisation de la mise en gage sûre. Pour parvenir à ce résultat, nous introduisons la notion de purification intrinsèque, qui permet de contourner l'utilisation du théorème de Uhlman, en particulier dans le cas gaussien. Nous examinons ensuite une primitive cryptographique plus faible, le ``tirage faible à pile ou face'', dans le modèle standard du calcul quantique. Carlos Mochon a donné une preuve d'existence d'un tel protocole avec un biais arbitrairement petit. Nous donnons une interprétation claire de sa preuve, ce qui nous permet de la simplifier et de la raccourcir grandement.La seconde partie de cette thèse concerne l'étude de méthodes pour prouver des bornes inférieures dans le modèle de la complexité en requête. Il s'agit d'un modèle de complexité central en calcul quantique dans lequel de nombreux résultats majeurs ont été obtenus. Dans ce modèle, un algorithme ne peut accéder à l'entrée uniquement en effectuant des requêtes sur chacun des bits de l'entrée. Nous considérons une extension de ce modèle dans lequel un algorithme ne calcule pas une fonction, mais doit générer un état quantique. Cette généralisation nous permet de comparer les différentes méthodes pour prouver des bornes inférieures dans ce modèle. Nous montrons d'abord que la méthode par adversaire ``multiplicative" est plus forte que la méthode ``additive". Nous montrons ensuite une réduction de la méthode polynomiale à la méthode multiplicative, ce qui permet de conclure à la supériorité de la méthode par adversaire multiplicative sur toutes les autres méthodes. Les méthodes par adversaires sont en revanche souvent difficiles à utiliser car elles nécessite le calcul de normes de matrices de très grandes tailles. Nous montrons comment l'étude des symétries d'un problème simplifie grandement ces calculs. Enfin, nous appliquons ces formules pour prouver la borne inférieure optimale du problème INDEX-ERASURE un problème de génération d'état quantique lié au célèbre problème GRAPH-ISOMORPHISM.
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é.
Les mesures complexes à travers le prisme des jeux à deux joueurs et des signatures de l'hypercube Les mesures de complexité des fonctions booléennes capturent divers aspects de la difficulté du calcul d'une fonction et leur étude consiste à trouver des connexions entre différentes mesures de complexité. Dans la première partie de cette thèse, nous introduisons et étudions la complexité de jeux de certificats, une mesure de complexité basée sur la probabilité de gagner un jeu dans lequel deux joueurs reçoivent des entrées avec des valeurs de fonctions différentes et doivent produire un indice i pour lequel leurs entrées diffèrent, sans communiquer. Nous donnons des bornes supérieures et inférieures pour les stratégies à base de pièces privées, de pièces publiques, d'intrication partagée et de non-signalisation, et nous prouvons quelques résultats de séparations. D'une part, nous montrons que la complexité dans le cas des pièces publiques est majorée par les complexités de requête aléatoire et de certificat. D'autre part, nous montrons qu'elle est minorée par la complexité fractionnelle de certificat, ce qui en fait un bon candidat pour trouver des bornes inférieures fortes sur la complexité de requête aléatoire. La complexité dans le cas des pièces privées est minorée par la complexité de requête aléatoire à erreur nulle. Nous utilisons la non-signalisation, une notion d'information quantique, pour minorer par n la complexité de jeux de certificats quantiques de la fonction OR, dont la complexité de requête quantique est de Θ(√n), puis nous montrons que ce "goulot d'étranglement de non-signalisation" s'applique à toutes les fonctions à sensibilité, à sensibilité de bloc ou à sensibilité de bloc fractionnaire élevée. Nous considérons également la version mono-bit des jeux de certificats, où les entrées des deux joueurs sont restreints à une distance de Hamming de 1. Nous prouvons que la version mono-bit de la complexité de jeux de certificats avec aléa partagé est égale à la sensibilité à un facteur constant près, ce qui donne une nouvelle caractérisation de la sensibilité. D'autre part, la version mono-bit de la complexité de jeux de certificats avec aléa privé est égale à λ2, où λ est la sensibilité spectrale. Dans la deuxième partie de cette thèse, nous revisitons la célèbre preuve de la conjecture de la sensibilité par Hao Huang. En utilisant des techniques spectrales, Huang a prouvé que tout sous-graphe de l'hypercube Hn de dimension n induit sur plus de la moitié des sommets a un degré maximal d'au moins √n. Combiné avec des travaux antérieurs, ce résultat a complété une preuve de la conjecture de la sensibilité. Nous en donnons une preuve alternative en utilisant seulement la dépendance linéaire des vecteurs associés aux sommets de l'hypercube. Notre approche permet de mieux comprendre les propriétés structurelles du sous-graphe induit, en plus du plus grand degré. En particulier, nous prouvons que dans tout sous-graphe induit de Hn avec plus de la moitié du nombre de sommets, il existe deux sommets, l'un de parité impaire et l'autre de parité paire, chacun ayant au moins n sommets à une distance au plus égale à 2. Comme application, nous montrons que pour toute fonction booléenne f, le degré polynomial est majoré par le produit de la sensibilité 0 et de la sensibilité 1, s0(f)s1(f), une affirmation strictement plus forte qui implique le théorème de Huang. Nous obtenons également des relations structurelles pour les sous-graphes induits à distance 3. Un ingrédient clé de la preuve de Huang était des hypercubes signés avec la propriété que chaque cycle de longueur 4 est affecté d'un signe négatif. Nous examinons en détail cette signature et donnons une signature quasi-optimale qui utilise le nombre minimum de bords négatifs tout en garantissant que chaque cycle de longueur 4 est négatif. Ce problème s'avère être lié à l'un des problèmes d'Erdös sur le plus grand sous-graphe de l'hypercube exempt de 4-cycles.
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.
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.