Depuis son invention en 1984 par C.H. Bennett et G. Brassard, le protocole BB84 a été prouvé sûr contre les attaques les plus générales autorisées par la mécanique quantique, les attaques cohérentes. Cependant, afin de réaliser ces attaques, un adversaire a besoin de mémoire quantique et il n'existe pas à l'heure actuelle de technologie permettant de créer facilement de telles mémoires. Il est donc important de savoir quantifier plus précisément la puissance de l'adversaire lorsque celui-ci n'a pas accès à une mémoire quantique parfaite. Ces nouveaux modèles de sécurité où la puissance de l'adversaire est limitée par des contraintes plus ou moins fortes sur sa mémoire quantique ont été déjà développés et utilisés pour étudier la sécurité des protocoles réalisant une fonction cryptographique à deux participants (comme la mise en gage de bit quantique par exemple). L'objectif de cette thèse a été d'adapter ces modèles de sécurité à l'étude de la sécurité des protocoles de distribution quantique de clés. Nous avons ainsi pu étudier la sécurité des principaux protocoles de distribution quantique de clés dans le cas où l'adversaire n'a pas de mémoire quantique et dans un modèle plus général où il est limité par le bruit de sa mémoire. Ces recherches ont permis de mieux comprendre l'influence de la qualité de la mémoire quantique sur la puissance des attaques et ainsi de quantifier le compromis entre la performance d'un protocole (en terme de taux de clé ou de distance atteignable) et la sécurité désirée.
Depuis son invention en 1984 par C.H. Bennett et G. Brassard, le protocole BB84 a été prouvé sûr contre les attaques les plus générales autorisées par la mécanique quantique, les attaques cohérentes. Cependant, afin de réaliser ces attaques, un adversaire a besoin de mémoire quantique et il n'existe pas à l'heure actuelle de technologie permettant de créer facilement de telles mémoires. Il est donc important de savoir quantifier plus précisément la puissance de l'adversaire lorsque celui-ci n'a pas accès à une mémoire quantique parfaite. Ces nouveaux modèles de sécurité où la puissance de l'adversaire est limitée par des contraintes plus ou moins fortes sur sa mémoire quantique ont été déjà développés et utilisés pour étudier la sécurité des protocoles réalisant une fonction cryptographique à deux participants (comme la mise en gage de bit quantique par exemple). L'objectif de cette thèse a été d'adapter ces modèles de sécurité à l'étude de la sécurité des protocoles de distribution quantique de clés. Nous avons ainsi pu étudier la sécurité des principaux protocoles de distribution quantique de clés dans le cas où l'adversaire n'a pas de mémoire quantique et dans un modèle plus général où il est limité par le bruit de sa mémoire. Ces recherches ont permis de mieux comprendre l'influence de la qualité de la mémoire quantique sur la puissance des attaques et ainsi de quantifier le compromis entre la performance d'un protocole (en terme de taux de clé ou de distance atteignable) et la sécurité désirée.
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.
La cryptographie fondée sur les réseaux euclidiens représente une alternative prometteuse à la cryptographie asymétrique utilisée actuellement, en raison de sa résistance présumée à un ordinateur quantique universel. Cette nouvelle famille de schémas asymétriques dispose de plusieurs atouts parmi lesquels de fortes garanties théoriques de sécurité, un large choix de primitives et, pour certains de ses représentants, des performances comparables aux standards actuels. Une campagne de standardisation post-quantique organisée par le NIST est en cours et plusieurs schémas utilisant des réseaux euclidiens font partie des favoris. La communauté scientifique a été encouragée à les analyser car ils pourraient à l'avenir être implantés dans tous nos systèmes. L'objectif de cette thèse est de contribuer à cet effort. Nous étudions la sécurité de ces nouveaux cryptosystèmes non seulement au sens de leur résistance à la cryptanalyse en ''boîte noire'' à l'aide de moyens de calcul classiques, mais aussi selon un spectre plus large de modèles de sécurité, comme les attaques quantiques, les attaques supposant des failles d'utilisation, ou encore les attaques par canaux auxiliaires. Ces différents types d’attaques ont déjà été largement formalisés et étudiés par le passé pour des schémas asymétriques et symétriques pré-quantiques. Dans ce mémoire, nous analysons leur application aux nouvelles structures induites par les réseaux euclidiens. Notre travail est divisé en deux parties complémentaires : les contremesures et les attaques. La première partie regroupe nos contributions à l'effort actuel de conception de nouvelles protections algorithmiques afin de répondre aux nombreuses publications récentes d’attaques par canaux auxiliaires. Les travaux réalisés en équipe auxquels nous avons pris part on abouti à l'introduction de nouveaux outils mathématiques pour construire des contre-mesures algorithmiques, appuyées sur des preuves formelles, qui permettent de prévenir systématiquement les attaques physiques et par analyse de temps d'exécution. Nous avons ainsi participé à la protection de plusieurs schémas de signature fondés sur les réseaux euclidiens comme GLP, BLISS, qTesla ou encore Falcon. Dans une seconde partie consacrée à la cryptanalyse, nous étudions dans un premier temps de nouvelles attaques qui tirent parti du fait que certains schémas de chiffrement à clé publique ou d'établissement de clé peuvent échouer avec une faible probabilité. Ces échecs sont effectivement faiblement corrélés au secret. Notre travail a permis d’exhiber des attaques dites « par échec de déchiffrement » dans des modèles de failles d'utilisation ou des modèles quantiques. Nous avons d'autre part introduit un outil algorithmique de cryptanalyse permettant d’estimer la sécurité du problème mathématique sous-jacent lorsqu’une information partielle sur le secret est donnée. Cet outil s’est avéré utile pour automatiser et améliorer plusieurs attaques connues comme des attaques par échec de déchiffrement, des attaques classiques ou encore des attaques par canaux auxiliaires.
La mécanique quantique offre un avantage indéniable sur la mécanique classique pour la réalisation de diverses tâches cryptographiques. Cependant, elle ouvre également la voie à des attaques complexes qui compliquent l’analyse des protocoles cryptographiques. Ainsi, les cryptographes sont constamment à la recherche de nouveaux outils qui permettent de simplifier les preuves. Dans cette thèse, nous introduisons de nouvelles techniques qui permettent de simplifier l’analyse de protocoles cryptographiques quantiques et nous en démontrons l’utilité par quelques exemples d’applications. Nos techniques permettent de montrer que, sous certaines conditions, la sûreté d’un protocole cryptographique contre une attaque qui respecte plus ou moins le protocole (passive) est une condition suffisante pour montrer la sûreté contre une attaque qui peut dévier du protocole (active). Nous montrons d’abord que la sécurité d’un protocole quantique contre les adversaires sans mémoire quantique implique sa sécurité contre les adversaires disposant d’une certaine quantité de mémoire. Cette technique trouve son utilité dans le fait que les attaques ayant accès à une mémoire quantique sont généralement bien plus difficiles à analyser que celles sans mémoire. Nous introduisons ensuite la certification d’états mixtes : étant donné un registre quantique composé de n qubits, nous montrons qu’il est possible de s’assurer que ce registre est près de n copies d’une même matrice de densité φ. Cet outil offre un cadre général pour analyser une situation commune en cryptographie quantique où une source non fiable fournit un état quantique et on veut s’assurer que l’état fourni par cette source est le bon. Ces résultats ont permis de contribuer aux connaissances en cryptographie quantique par les avancées suivantes. D’abord, nous résolvons deux problèmes ouverts, l’un concernant la puissance cryptographique de la primitive cut-and-choose à un bit, et l’autre concernant la sûreté du protocole de mise en gage BCJL. Dans les deux cas, notre relation entre les adversaires quantiques et les adversaires sans mémoire joue un rôle central. Par la suite, nous introduisons une nouvelle tâche cryptographique où deux participants veulent générer une chaine de bits commune quasi uniformément distribuée, et ce même si l’un des participants est malhonnête. Nous présentons un protocole quantique qui surpasse tout protocole classique pour cette tâche.
Sécurité étendue de la cryptographie fondée sur les réseaux Euclidiens La cryptographie fondée sur les réseaux euclidiens représente une alternative prometteuse à la cryptographie asymétrique utilisée actuellement, en raison de sa résistance présumée à un ordinateur quantique universel. Cette nouvelle famille de schémas asymétriques dispose de plusieurs atouts parmi lesquels de fortes garanties théoriques de sécurité, un large choix de primitives et, pour certains de ses représentants, des performances comparables aux standards actuels. Une campagne de standardisation post-quantique organisée par le NIST est en cours et plusieurs schémas utilisant des réseaux euclidiens font partie des favoris. La communauté scientifique a été encouragée à les analyser car ils pourraient à l'avenir être implantés dans tous nos systèmes. L'objectif de cette thèse est de contribuer à cet effort. Nous étudions la sécurité de ces nouveaux cryptosystèmes non seulement au sens de leur résistance à la cryptanalyse en ''boîte noire'' à l'aide de moyens de calcul classiques, mais aussi selon un spectre plus large de modèles de sécurité, comme les attaques quantiques, les attaques supposant des failles d'utilisation, ou encore les attaques par canaux auxiliaires. Ces différents types d’attaques ont déjà été largement formalisés et étudiés par le passé pour des schémas asymétriques et symétriques pré-quantiques. Dans ce mémoire, nous analysons leur application aux nouvelles structures induites par les réseaux euclidiens. Notre travail est divisé en deux parties complémentaires : les contremesures et les attaques. La première partie regroupe nos contributions à l'effort actuel de conception de nouvelles protections algorithmiques afin de répondre aux nombreuses publications récentes d’attaques par canaux auxiliaires. Les travaux réalisés en équipe auxquels nous avons pris part on abouti à l'introduction de nouveaux outils mathématiques pour construire des contre-mesures algorithmiques, appuyées sur des preuves formelles, qui permettent de prévenir systématiquement les attaques physiques et par analyse de temps d'exécution. Nous avons ainsi participé à la protection de plusieurs schémas de signature fondés sur les réseaux euclidiens comme GLP, BLISS, qTesla ou encore Falcon. Dans une seconde partie consacrée à la cryptanalyse, nous étudions dans un premier temps de nouvelles attaques qui tirent parti du fait que certains schémas de chiffrement à clé publique ou d'établissement de clé peuvent échouer avec une faible probabilité. Ces échecs sont effectivement faiblement corrélés au secret. Notre travail a permis d’exhiber des attaques dites « par échec de déchiffrement » dans des modèles de failles d'utilisation ou des modèles quantiques. Nous avons d'autre part introduit un outil algorithmique de cryptanalyse permettant d’estimer la sécurité du problème mathématique sous-jacent lorsqu’une information partielle sur le secret est donnée. Cet outil s’est avéré utile pour automatiser et améliorer plusieurs attaques connues comme des attaques par échec de déchiffrement, des attaques classiques ou encore des attaques par canaux auxiliaires.
La cryptographie moderne a un ennemi de taille à l'horizon : la montée inévitable des ordinateurs quantiques. Cependant, cette même puissance de calcul permettrait également de trouver des solutions sur des tâches cryptographiques qui sont tout simplement impossibles à réaliser avec la technologie actuelle. Dans cette thèse, nous mettons les pieds dans un univers où le quantique est omniprésent en y présentant notamment deux principales contributions. Nous mettons en avant à la fois des nouveaux modèles et de nouvelles analyses de sécurité pour deux primitives cryptographiques : les chiffrements et les preuves à divulgation nulle de connaissance non interactives. Les définitions usuelles de sécurité de ces primitives requièrent intrinsèquement la capacité d'enregistrer et de comparer des chaînes classiques. Cependant, les tâches d'enregistrement et de comparaison sont extrêmement difficiles dans le monde quantique en raison du principe d'incertitude. Nous proposons deux alternatives afin de surmonter cette barrière. De plus, nos notions de sécurité sont les premières à prendre pleinement en compte les attaques quantiques dans lesquelles les attaquants peuvent interagir avec les utilisateurs finaux sur des canaux quantiques. D'autre part, nous montrons que la disponibilité des ordinateurs quantiques se révèle être également à l'avantage des cryptographes, même lorsque les utilisateurs finaux n'utilisent que des communications classiques. En particulier, nous présentons un protocole interactif entre une Alice classique et un Bob quantique. Ce dispositif permet à Alice d'envoyer un état quantique caché non clonable à Bob par des canaux classiques. En outre, cet état quantique non clonable établit une forte propriété dite de monogamie de l'intrication, qui décrit les limites de la force des corrélations multipartites quantiques. Enfin, nous appliquons notre protocole et nous donnons les premiers schémas semi-quantiques de protection contre la copie.
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.