Jeux non-locaux au travers de la complexité de la communication et de la cryptographie quantique Cette thèse explore des aspects fondamentaux de la théorie de l'information quantique et de la cryptographie quantique. D'une part, nous étudions les corrélations quantiques dans des contextes interactifs, notamment les jeux de CHSH et d'isomorphisme de graphes. Notre objectif est de distinguer les corrélations quantiques des corrélations non-signalantes en nous appuyant sur le principe de complexité de la communication. Pour cela, nous utilisons des techniques telles que le calcul distribué, l'amplification de biais grâce à la fonction majorité, les propriétés algébriques et géométriques des câblages de boîtes non-locales, ainsi que des variantes de certaines propriétés de graphes comme l'isomorphisme, la transitivité et les partitions équitables. Cette étude fait progresser notre compréhension des corrélations non-physiques. D'autre part, nous abordons un problème ouvert majeur en cryptographie : la faisabilité du chiffrement non-clonable. Notre objectif est de construire un schéma de chiffrement qui empêche deux réceptionneurs distants l'un de l'autre d'obtenir simultanément de l'information sur un message chiffré partagé. Nous introduisons un candidat au chiffrement non-clonable dans le modèle standard, c'est-à-dire sans hypothèse, en vue d'obtenir une preuve inconditionnelle de la sécurité. Notre protocole repose sur l'algèbre de Clifford et utilise des matrices unitaires hermitiennes à coefficients complexes qui anti-commutent. Pour des tailles de clés réduites, nous prouvons rigoureusement la sécurité à l'aide de méthodes de sommes de carrés, tandis que pour des tailles de clés plus grandes, nous fournissons des validations numériques solides via la hiérarchie NPA.
Jeux non-locaux au travers de la complexité de la communication et de la cryptographie quantique Cette thèse explore des aspects fondamentaux de la théorie de l'information quantique et de la cryptographie quantique. D'une part, nous étudions les corrélations quantiques dans des contextes interactifs, notamment les jeux de CHSH et d'isomorphisme de graphes. Notre objectif est de distinguer les corrélations quantiques des corrélations non-signalantes en nous appuyant sur le principe de complexité de la communication. Pour cela, nous utilisons des techniques telles que le calcul distribué, l'amplification de biais grâce à la fonction majorité, les propriétés algébriques et géométriques des câblages de boîtes non-locales, ainsi que des variantes de certaines propriétés de graphes comme l'isomorphisme, la transitivité et les partitions équitables. Cette étude fait progresser notre compréhension des corrélations non-physiques. D'autre part, nous abordons un problème ouvert majeur en cryptographie : la faisabilité du chiffrement non-clonable. Notre objectif est de construire un schéma de chiffrement qui empêche deux réceptionneurs distants l'un de l'autre d'obtenir simultanément de l'information sur un message chiffré partagé. Nous introduisons un candidat au chiffrement non-clonable dans le modèle standard, c'est-à-dire sans hypothèse, en vue d'obtenir une preuve inconditionnelle de la sécurité. Notre protocole repose sur l'algèbre de Clifford et utilise des matrices unitaires hermitiennes à coefficients complexes qui anti-commutent. Pour des tailles de clés réduites, nous prouvons rigoureusement la sécurité à l'aide de méthodes de sommes de carrés, tandis que pour des tailles de clés plus grandes, nous fournissons des validations numériques solides via la hiérarchie NPA.
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.
La théorie de l'information quantique s'est développée à une vitesse fulgurante au cours des vingt dernières années, avec des analogues et extensions des théorèmes de codage de source et de codage sur canal bruité pour la communication unidirectionnelle. Pour la communication interactive, un analogue quantique de la complexité de la communication a été développé, pour lequel les protocoles quantiques peuvent performer exponentiellement mieux que les meilleurs protocoles classiques pour certaines tâches classiques. Cependant, l'information quantique est beaucoup plus sensible au bruit que l'information classique. Il est donc impératif d'utiliser les ressources quantiques à leur plein potentiel. Dans cette thèse, nous étudions les protocoles quantiques interactifs du point de vue de la théorie de l'information et étudions les analogues du codage de source et du codage sur canal bruité. Le cadre considéré est celui de la complexité de la communication: Alice et Bob veulent faire un calcul quantique biparti tout en minimisant la quantité de communication échangée, sans égard au coût des calculs locaux. Nos résultats sont séparés en trois chapitres distincts, qui sont organisés de sorte à ce que chacun puisse être lu indépendamment. Étant donné le rôle central qu'elle occupe dans le contexte de la compression interactive, un chapitre est dédié à l'étude de la tâche de la redistribution d'état quantique. Nous prouvons des bornes inférieures sur les coûts de communication nécessaires dans un contexte interactif. Nous prouvons également des bornes atteignables avec un seul message, dans un contexte d'usage unique. Dans un chapitre subséquent, nous définissons une nouvelle notion de complexité de l'information quantique. Celle-ci caractérise la quantité d'information, plutôt que de communication, qu'Alice et Bob doivent échanger pour calculer une tâche bipartie. Nous prouvons beaucoup de propriétés structurelles pour cette quantité, et nous lui donnons une interprétation opérationnelle en tant que complexité de la communication quantique amortie. Dans le cas particulier d'entrées classiques, nous donnons une autre caractérisation permettant de quantifier le coût encouru par un protocole quantique qui oublie de l'information classique. Deux applications sont présentées: le premier résultat général de somme directe pour la complexité de la communication quantique à plus d'une ronde, ainsi qu'une borne optimale, à un terme polylogarithmique près, pour la complexité de la communication quantique avec un nombre de rondes limité pour la fonction « ensembles disjoints ». Dans un chapitre final, nous initions l'étude de la capacité interactive quantique pour les canaux bruités. Étant donné que les techniques pour distribuer de l'intrication sont bien étudiées, nous nous concentrons sur un modèle avec intrication préalable parfaite et communication classique bruitée. Nous démontrons que dans le cadre plus ardu des erreurs adversarielles, nous pouvons tolérer un taux d'erreur maximal de une demie moins epsilon, avec epsilon plus grand que zéro arbitrairement petit, et ce avec un taux de communication positif. Il s'ensuit que les canaux avec bruit aléatoire ayant une capacité positive pour la transmission unidirectionnelle ont une capacité positive pour la communication interactive quantique. Nous concluons avec une discussion de nos résultats et des directions futures pour ce programme de recherche sur une théorie de l'information quantique interactive.
Protocoles pratiques pour les réseaux de communication quantique Dans cette thèse, nous étudions les réseaux des états optiques quantiques intriqués avec différents degrés de complexité, avec une attention particulière portée à leur application dans des scénarios de communication quantique. Le but de la communication quantique est de permettre à deux ou plusieurs parties de communiquer d'une façon qui serait impossible avec de la technologie classique. L'archétype de ce domaine est la distribution de clé quantique ou quantum key distribution (QKD), qui permet à deux agents de partager une clé aléatoire secrète pour effectuer des communications sécurisées, en empêchant, au même temps, qu'un troisième agent malveillant puisse obtenir connaissance de leur clé. Dans ce manuscrit, cependant, nous explorons des scénarios de communication quantique qui vont au-delà de la QKD standard afin de tester les nombreuses possibilités offertes par les réseaux de dispositifs quantiques interconnectés, aussi appelés internet quantique. Spécifiquement, nous présentons trois types de réseaux quantiques, qui correspondent à trois niveaux de complexité d'internet quantique. Dans chaque niveau, nous décrivons le scénario de communication, les exigences physiques nécessaires pour construire l'architecture spécifique et un nouveau protocole qui ne peut pas être reproduit sans des ressources quantiques. Dans cette document, nous veillons particulièrement à la "praticité" des protocoles, notamment le fait que leur implémentation doit être possible dans des conditions réalistes avec technologie existante, au moins comme preuve du principe. Le premier concerne un protocole quantique à preuves interactives qui montre pour la première fois une preuve expérimentale d'un avantage quantique dans un cadre interactif. Dans ce scénario, il y a un prouveur avec de la puissance calculatoire illimitée qui veut convaincre un vérifieur honnête de l'existence d'une certaine solution d'un problème mathématique complexe, en lui envoyant une partie de la preuve sous forme d'états quantiques. Notre construction permet au vérifieur de vérifier l'assertion du prouveur sans recevoir la solution entière. Nous prouvons que sans ressources quantiques, le protocole de vérification exigerait un temps exponentiel en la taille de la solution, menant à un avantage quantique en terme de temps de calcul, avantage que nous avons démontré dans notre laboratoire. Le deuxième porte sur un protocole de vote électronique qui exploite un état quantique multipartite intriqué non fiable pour réaliser une élection sans s'appuyer sur des autorités électorales, dont le résultat peut être vérifié publiquement sans compromettre la robustesse de la construction et qui peut être implémenté aisément avec les technologies de pointe existantes pour un petit nombre de votant. À l'invers des résultats précédents, notre protocole n'exige pas une émission simultanée et marche aussi dans des scénarios bruyants, où la sécurité est limitée par la fidélité de l'état quantique utilisé. Enfin, nous simulons des états comprimés de la lumière de nombreux modes comme des réseaux quantique Gaussien à variables continues avec des topologies complexes, nous caractérisons leur corrélations et nous estimons l'intensification de leur coût pendant que les réseaux grandissent avec une théorie de ressource de compression. Nous prouvons un résultat qui permet de renforcer l'intrication entre deux nœuds du réseau si on mesure les chemins multiples qui les connectent et nous utilisons cet effet pour concevoir un protocole de routage d'intrication dont les performance sont particulièrement efficace dans des réseaux complexes grands.
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.
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.
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.