Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Interactive hashing against quantum adversaries

Thibodeau, Louis-Charles

Published Aug 1, 2025• 0 citations
Publisher

Abstract

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.

DOI
10.71781/10031

Related papers

La securite des protocoles de la cryptographie quantique

Gilles Brassard, Dominic Mayers

Cette these s'est elaboree dans cette periode de l'histoire de la cryptographie quantique ou plusieurs protocoles avaient ete proposes sans que leur fiabilite n'ait pu etre encore demontree, du moins pas face a toute attaque. De plus, certaines des attaques qui avaient ete mises de cote etaient en fait accessibles a l'aide de la technologie actuelle. D'un autre cote, le but de la cryptographie quantique a toujours ete la conception de protocoles inconditionnellement fiables, cest-a-dire, fiables face a toute attaque permise par les lois de la physique sans consideration pour aucune contrainte dans le temps ou dans l'espace. Tel etait le niveau de fiabilite espere des protocoles quantiques proposes. Seule la cryptographie quantique pouvait meme oser offrir un tel niveau de securite. Une certaine application appelee la mise en gage jouait un role primordial dans l'ensemble des applications proposees par les cryptographes quantiques et une preuve de securite inconditionnelle avait ete proposee par Brassard, Crepeau, Jozsa et Langlois pour un protocole realisant cette tache. Notre objectif de depart etait de demontrer que les protocoles de la cryptographie quantique permettent effectivement de realiser avec une securite inconditionnelle la plupart des applications proposees, pas seulement la mise en gage. Cependant, a notre grande surprise et a l'etonnement de plusieurs, nous avons au contraire demontre qu'un protocole quantique de mise en gage inconditionnelle fiable est impossible et ainsi avons remis serieusement en question une partie importante des applications de la cryptographie quantique, en plus d'avoir demoli la preuve mentionnee plus haut. Par contre, en nous appuyant sur les travaux de Bennett, Brassard, Crepeau, Salvail et plus recemment de Yao, nous avons obtenu une preuve de la securite inconditionnelle d'un protocole quantique de distribution de cle. Un des principes importants que nous avons utilises dans notre these est celui qui dit que tous les phenomenes peuvent etre decrits comme l'execution d'une mesure quantique. De plus, nous avons utilise le fait que cette mesure peut elle-meme etre decrite comme une transformation unitaire sur le systeme qui est compose du systeme mesure, de l'appareil de mesure et du systeme final si celui-ci est different du systeme initial.

•Jan 1, 1996•2 citations

Quantum coin flipping and bit commitment : optimal bounds, pratical constructions and computational security

André Chailloux

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.

•Jun 24, 2011•0 citations

Protocoles quantiques et relativistes de mise en gage

Hassene Bada

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.

•Jan 1, 2009•0 citations

Dodging impossibilities in quantum cryptography : on the feasibility of one-time programs, signing quantum states, and cryptography without one-way functions

Mohammed Barhoush

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.

•Sep 1, 2026•0 citations

On the necessity of one-way functions in quantum cryptography

Vadacchino, Massimo

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

•Jan 1, 2025•0 citations

Lattice-based cryptography in a quantum setting : security proofs and attacks

Pouria Fallahpour

Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.

•Jul 5, 2024•1 citation
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.
Cette these s'est elaboree dans cette periode de l'histoire de la cryptographie quantique ou plusieurs protocoles avaient ete proposes sans que leur fiabilite n'ait pu etre encore demontree, du moins pas face a toute attaque. De plus, certaines des attaques qui avaient ete mises de cote etaient en fait accessibles a l'aide de la technologie actuelle. D'un autre cote, le but de la cryptographie quantique a toujours ete la conception de protocoles inconditionnellement fiables, cest-a-dire, fiables face a toute attaque permise par les lois de la physique sans consideration pour aucune contrainte dans le temps ou dans l'espace. Tel etait le niveau de fiabilite espere des protocoles quantiques proposes. Seule la cryptographie quantique pouvait meme oser offrir un tel niveau de securite. Une certaine application appelee la mise en gage jouait un role primordial dans l'ensemble des applications proposees par les cryptographes quantiques et une preuve de securite inconditionnelle avait ete proposee par Brassard, Crepeau, Jozsa et Langlois pour un protocole realisant cette tache. Notre objectif de depart etait de demontrer que les protocoles de la cryptographie quantique permettent effectivement de realiser avec une securite inconditionnelle la plupart des applications proposees, pas seulement la mise en gage. Cependant, a notre grande surprise et a l'etonnement de plusieurs, nous avons au contraire demontre qu'un protocole quantique de mise en gage inconditionnelle fiable est impossible et ainsi avons remis serieusement en question une partie importante des applications de la cryptographie quantique, en plus d'avoir demoli la preuve mentionnee plus haut. Par contre, en nous appuyant sur les travaux de Bennett, Brassard, Crepeau, Salvail et plus recemment de Yao, nous avons obtenu une preuve de la securite inconditionnelle d'un protocole quantique de distribution de cle. Un des principes importants que nous avons utilises dans notre these est celui qui dit que tous les phenomenes peuvent etre decrits comme l'execution d'une mesure quantique. De plus, nous avons utilise le fait que cette mesure peut elle-meme etre decrite comme une transformation unitaire sur le systeme qui est compose du systeme mesure, de l'appareil de mesure et du systeme final si celui-ci est different du systeme initial.
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.
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.
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
Cryptographie fondée sur les réseaux euclidiens dans une contexte quantique : preuves de sécurité et attaques L'émergence des machines quantiques crée des défis et des opportunités pour la cryptographie. En particulier, les preuves de sécurité doivent être révisées en raison des capacités quantiques des adversaires. Cette thèse propose deux contributions à cet égard : un résultat positif et un résultat négatif. La transformation de Fiat-Shamir avec des rejets est l’un des principaux paradigmes pour concevoir des schémas de signature post-quantiques. Une partie de cette thèse consiste en une analyse détaillée de cette transformation dans le modèle de l’oracle aléatoire quantique. Tous les travaux précédents proposant une analyse de sécurité de cette transformation ont négligé des détails subtils, compromettant la correction des preuves. Par conséquent, notre preuve de sécurité est la première de son genre à être correcte. De plus, nous analysons le temps d'exécution et la correction des signatures obtenues à partir de cette transformation. Le problème learning with errors (LWE) a été largement utilisé pour construire des schémas cryptographiques sécurisés contre les adversaires quantiques. Une hypothèse liée à LWE stipule que la génération d'une instance LWE sans connaître son secret est difficile pour tous les algorithmes polynomiaux. On peut utiliser cette hypothèse pour prouver la sécurité de certains arguments de connaissance succints. Bien que cela semble être une tâche difficile pour les algorithmes classiques, nous présentons un algorithme quantique polynomial qui génère des instances LWE sans connaître le secret. Notre algorithme invalide ainsi les analyses de sécurité de ces arguments de connaissance succints dans le contexte quantique.