Academic literature on the topic 'Protocoles de cryptographie quantique'

La cryptographie quantique, et plus particulièrement la distribution quantique de clés, promet la communication des données avec une sécurité absolue, indépendante des capacités d’un espion éventuel. Malgré des progrès significatifs, pour son utilisation dans une large gamme d’applications, des défis liés à la performance, le coût et la sécurité pratique des systèmes devront être abordés les prochaines années.

L’analyse des corrélations temporelles entre des photons se trouve au cœur des protocoles de traitement de l’information quantique (communication, métrologie et calcul) présentés dans ce dossier. Ces mesures de corrélation sont issues de techniques d’optique quantique fondamentale formalisées par R. Glauber en 1963 [Phys. Rev. 130, 2529] qui permettent de mesurer les propriétés des champs électromagnétiques et d’en détecter des régularités, des signatures dans un signal bruité. D’une façon plus générale, elles sont le résultat d’interférences d’ordre supérieur et sont, dans certains cas, directement reliées à la cohérence « classique » des champs optiques.

Je souhaite réaliser un modèle théorique optimal pour les protocoles de partage de secret quantique basé sur l'utilisation des états graphes. Le paramètre représentatif d'un partage de secret à seuil est, entre autres la taille du plus grand ensemble de joueurs qui ne peut pas accéder au secret. Je souhaite donc trouver un famille de protocoles pour laquelle ce paramètre est le plus petit possible. J'étudie également les liens entre les protocoles de partage de secret quantique et des familles de courbes en géométrie algébrique
I want to realize an optimal theoretical model for quantum secret sharing protocols based on graph states. The main parameter of a threshold quantum secret sharing scheme is the size of the largest set of players that can not access the secret. Thus, my goal is to find a collection of protocols for which the value of this parameter is the smallest possible. I also study the links between quantum secret sharing protocols and families of curves in algebraic geometry

La sécurité de la cryptographie à clés publiques repose sur des problèmes mathématiques difficiles, notamment en théorie des nombres, tels que la factorisation pour RSA ou le logarithme discret pour ElGamal. Cependant les progrès des algorithmes rendent les protocoles basés sur des problèmes de théorie des nombres de moins en moins efficaces. De plus, l'arrivée de l'ordinateur quantique rendrait ces cryptosystèmes inutilisables. La cryptographie basée sur les codes en métrique rang est une alternative crédible pour concevoir des cryptosystèmes post-quantiques en raison de sa rapidité et de la faible taille de ses clés. Le but de cette thèse est d'étudier les problèmes difficiles en métrique rang et les algorithmes permettant de les résoudre, ainsi que de chercher de nouvelles attaques et de nouvelles primitives basées sur ces problèmes
Security of public keys cryptography is based on difficult mathematic problems, especially in number field theory, such as the factorization for RSA or the discrete logarithm for ElGamal. However, algorithms are more and more efficient to solve these problems. Furthermore, quantum computers would be able to easily break these cryptosystems. Code-based cryptography in rank metric is a solid candidate to design new postquatum cryptosystems since it is fast and has low weight keysize. The goals of this thesis are to study hard problems in rank metric and algorithms which solve them, also to search for new attacks and new primitives based on these problems

Contrairement aux protocoles cryptographiques fondés sur la théorie des nombres, les systèmes de chiffrement basés sur les codes correcteurs d’erreurs semblent résister à l’émergence des ordinateurs quantiques. Un autre avantage de ces systèmes est que le chiffrement et le déchiffrement sont très rapides, environ cinq fois plus rapide pour le chiffrement, et 10 à 100 fois plus rapide pour le déchiffrement par rapport à RSA. De nos jours, l’intérêt de la communauté scientifique pour la cryptographie basée sur les codes est fortement motivé par la dernière annonce de la “National Institute of Standards and Technology" (NIST), qui a récemment initié le projet intitulé “Post-Quantum cryptography Project". Ce projet vise à définir de nouveaux standards pour les cryptosystèmes résistants aux attaques quantiques et la date limite pour la soumission des cryptosystèmes à clé publique est fixée pour novembre 2017. Une telle annonce motive certainement à proposer de nouveaux protocoles cryptographiques basés sur les codes, mais aussi à étudier profondément la sécurité des protocoles existants afin d’écarter toute surprise en matière de sécurité. Cette thèse suit cet ordre d’idée en étudiant la sécurité de plusieurs protocoles cryptographiques fondés sur la théorie des codes correcteurs d’erreurs. Nous avons commencé par l’étude de la sécurité d’une version modifiée du cryptosystème de Sidelnikov, proposée par Gueye et Mboup [GM13] et basée sur les codes de Reed-Muller. Cette modification consiste à insérer des colonnes aléatoires dans la matrice génératrice (ou de parité) secrète. La cryptanalyse repose sur le calcul de carrés du code public. La nature particulière des codes de Reed-Muller qui sont définis au moyen de polynômes multivariés binaires, permet de prédire les valeurs des dimensions des codes carrés calculés, puis permet de récupérer complètement en temps polynomial les positions secrètes des colonnes aléatoires. Notre travail montre que l’insertion de colonnes aléatoires dans le schéma de Sidelnikov n’apporte aucune amélioration en matière de sécurité. Le résultat suivant est une cryptanalyse améliorée de plusieurs variantes du cryptosystème GPT qui est un schéma de chiffrement en métrique rang utilisant les codes de Gabidulin. Nous montrons qu’en utilisant le Frobenius de façon appropriée sur le code public, il est possible d’en extraire un code de Gabidulin ayant la même dimension que le code de Gabidulin secret mais avec une longueur inférieure. Le code obtenu corrige ainsi moins d’erreurs que le code secret, mais sa capacité de correction d’erreurs dépasse le nombre d’erreurs ajoutées par l’expéditeur et par conséquent, un attaquant est capable de déchiffrer tout texte chiffré, à l’aide de ce code de Gabidulin dégradé. Nos résultats montrent qu’en fin de compte, toutes les techniques existantes visant à cacher la structure algébrique des codes de Gabidulin ont échoué. Enfin, nous avons étudié la sécurité du système de chiffrement de Faure-Loidreau [FL05] qui est également basé sur les codes de Gabidulin. Inspiré par les travaux précédents et, bien que la structure de ce schéma diffère considérablement du cadre classique du cryptosystème GPT, nous avons pu montrer que ce schéma est également vulnérable à une attaque polynomiale qui récupère la clé privée en appliquant l’attaque d’Overbeck sur un code public approprié. Comme exemple, nous arrivons en quelques secondes à casser les paramètres qui ont été proposés comme ayant un niveau de sécurité de 80 bits
Contrary to the cryptosystems based on number theory, the security of cryptosystems based on error correcting codes appears to be resistant to the emergence of quantum computers. Another advantage of these systems is that the encryption and decryption are very fast, about five times faster for encryption, and 10 to 100 times faster for decryption compared to RSA cryptosystem. Nowadays, the interest of scientific community in code-based cryptography is highly motivated by the latest announcement of the National Institute of Standards and Technology (NIST). They initiated the Post-Quantum cryptography Project which aims to define new standards for quantum resistant cryptography and fixed the deadline for public key cryptographic algorithm submissions for November 2017. This announcement motivates to study the security of existing schemes in order to find out whether they are secure. This thesis thus presents several attacks which dismantle several code-based encryption schemes. We started by a cryptanalysis of a modified version of the Sidelnikov cryptosystem proposed by Gueye and Mboup [GM13] which is based on Reed-Muller codes. This modified scheme consists in inserting random columns in the secret generating matrix or parity check matrix. The cryptanalysis relies on the computation of the square of the public code. The particular nature of Reed-Muller which are defined by means of multivariate binary polynomials, permits to predict the values of the dimensions of the square codes and then to fully recover in polynomial time the secret positions of the random columns. Our work shows that the insertion of random columns in the Sidelnikov scheme does not bring any security improvement. The second result is an improved cryptanalysis of several variants of the GPT cryptosystem which is a rank-metric scheme based on Gabidulin codes. We prove that any variant of the GPT cryptosystem which uses a right column scrambler over the extension field as advocated by the works of Gabidulin et al. [Gab08, GRH09, RGH11] with the goal to resist Overbeck’s structural attack [Ove08], are actually still vulnerable to that attack. We show that by applying the Frobeniusoperator appropriately on the public key, it is possible to build a Gabidulin code having the same dimension as the original secret Gabidulin code, but with a lower length. In particular, the code obtained by this way corrects less errors than thesecret one but its error correction capabilities are beyond the number of errors added by a sender, and consequently an attacker is able to decrypt any ciphertext with this degraded Gabidulin code. We also considered the case where an isometrictransformation is applied in conjunction with a right column scrambler which has its entries in the extension field. We proved that this protection is useless both in terms of performance and security. Consequently, our results show that all the existingtechniques aiming to hide the inherent algebraic structure of Gabidulin codes have failed. To finish, we studied the security of the Faure-Loidreau encryption scheme [FL05] which is also a rank-metric scheme based on Gabidulin codes. Inspired by our precedent work and, although the structure of the scheme differs considerably from the classical setting of the GPT cryptosystem, we show that for a range of parameters, this scheme is also vulnerable to a polynomial-time attack that recovers the private key by applying Overbeck’s attack on an appropriate public code. As an example we break in a few seconds parameters with 80-bit security claim

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
This thesis stands at the interface between quantum theory and experiments, focusing on practical protocols that can be implemented using present-day technology. Our goal is to build a general framework for the design and implementation of quantum cryptographic schemes that will improve the safety of future telecommunication networks. In addition, this thesis aims to advance research on quantum physics and computer science, by improving our understanding of entanglement. The correlations of entangled states can not be reproduced by conventional means, allowing to perform tasks (eg teleportation and superdense coding) that are otherwise impossible. It is therefore of major importance to be able to check whether a quantum state is entangled. In this thesis, we show how to efficiently check whether a physical source can create multi-party entangled states and share them with many parties, some of which are dishonest and work with the source. This protocol could prove essential for quantum computation between suspicious parties and could also facilitate the secure delegation of tasks to powerful untrusted quantum servers. Finally, we study the link between game theory and quantum non-locality, in the context of Bayesian games. We examine how the shared entanglement helps players win a game with a higher probability than the conventional resources could achieve

La cryptographie quantique a bénéficié des nombreuses avancées de la cryptographie et théorie des réseaux classiques. Cependant, elle n’en est qu’à ses balbutiement en ce qui concerne son application en condition réelles et approfondir la théorie sous-jacente est un prérequis crucial à l’exploitation de l’intégralité de ses possibilités. Pour cela, il faut tout d’abord formaliser rigoureusement les propriétés de sécurité quantiques des techniques importées de la cryptographie classique, pour l’instant souvent utilisées sans justification. Ensuite, les progrès récents des technologies quantiques tendent à pointer vers un modèle d’accès type client-serveur avec un client faiblement quantique. Dans ce contexte, les protocoles quantiques se doivent d’être les plus frugaux possibles en termes de ressources (mémoire et opération). Enfin, implémenter des protocoles sur des architectures concrètes nécessite de les adapter finement aux machines utilisées afin d’améliorer encore leur optimisation. Cette thèse contribue à ces trois aspects en : (i) proposant une définition du Quantum Cut-and-Choose, technique qui permet de garantir la préparation honnête d’un message quantique ; (ii) présentant un cadre de sécurité plus réaliste contre les attaques par superposition, qui garantit la sécurité de protocoles classiques exécutés sur une machine quantique ; (iii) construisant un protocole efficace de délégation de calcul multipartite quantique, qui permet à des clients de déléguer un calcul privé à un serveur ; (iv) démontrant qu’il est possible de vérifier l’exactitude de calculs quantiques délégués sans aucun impact en terme ressources côté client ou serveur
Quantum cryptography builds upon decades of advances both in classical cryptography and networks. However, contrary to its classical counterparts, it is still in its infancy applicability-wise, even in the scenario where powerful quantum computers are readily available, and more theoretical work is required before it can provide concrete benefits. The first goal is to formalise in rigorous quantum security frameworks the properties of various techniques that have been transposed, often without proper justification, from the classical world.Then, the recent developments in quantum technologies suggest a mostly cloud-based future availability of quantum devices. Therefore, quantum computation and communication cost of protocol participants must be lowered before being useful.Finally, in most situations, additional steps need to be taken to tailor protocols to the specifications of devices. This allows for optimisations both in terms of quantum memory and operation requirements.This thesis contributes to these three aspects by: (i) giving the first general security definition of the Quantum Cut-and-Choose, a technique for proving the correctness of a quantum message; (ii) presenting a more realistic framework of security against superposition attacks, where classical protocols run on inherently quantum devices; (iii) constructing an efficient delegated multi-party quantum computation protocol, allowing clients to delegate securely to a quantum server a private computation; (iv) building a method for verifying the honesty of a quantum server performing computations on behalf of a client with no operation or memory overhead compared to the unprotected computation

Les ordinateurs quantiques promettent de surprenantes puissances de calcul en exploitant les étonnantes propriétés de particules infiniment petites. Je m'applique à prouver la sécurité de protocoles permettant à un client purement classique d'utiliser les ressources calculatoires d'un serveur quantique, de manière à ce que le calcul effectué ne soit jamais révélé au serveur. À cette fin, je développe un outil modulaire permettant de générer sur un serveur distant un état quantique que seul le client est en capacité de décrire, et je montre comment on peut générer plus efficacement des états quantiques sur plusieurs qubits. Je prouve également qu'il n'existe pas de protocoles de ce type qui soit sécurisé dans un modèle de sécurité généralement composable, y compris lorsque ce module est utilisé dans le protocole UBQC. Outre le calcul délégué, cet outil s’avère également être utile pour effectuer une tache qui pourrait paraître impossible à réaliser de prime abord: prouver des propriétés avancées sur un état quantique de manière non-interactive (un seul message est envoyé) et non-destructive (l'état quantique reçu est intact), y compris lorsque cet état est généré collaborativement par plusieurs participants. Cette propriété s'avère en particulier utile pour pouvoir filtrer les participants dans un protocole sans révéler leur identité, et peut avoir des applications dans d'autres domaines, par exemple pour transmettre un état quantique sur un réseau tout en cachant la source et la destination du message. Enfin, je discute de mes travaux indépendants en cours sur les programmes à usage unique, mêlant cryptographie quantique, codes correcteurs et théorie de l'information
Quantum computers promise surprising powers of computation by exploiting the stunning physical properties of infinitesimally small particles. I focused on designing and proving the security of protocols that allow a purely classical client to use the computational resources of a quantum server, so that the performed computation is never revealed to the server. To this end, I develop a modular tool to generate on a remote server a quantum state that only the client is able to describe, and I show how multi-qubits quantum states can be generated more efficiently. I also prove that there is no such protocol that is secure in a generally composable model of security, including when our module is used in the UBQC protocol. In addition to delegated computation, this tool also proves to be useful for performing a task that might seem impossible to achieve at first sight: proving advanced properties on a quantum state in a non-interactive and non-destructive way, including when this state is generated collaboratively by several participants. This can be seen as a quantum analogue of the classical Non-Interactive Zero-Knowledge proofs. This property is particularly useful to filter the participants of a protocol without revealing their identity, and may have applications in other domains, for example to transmit a quantum state over a network while hiding the source and destination of the message. Finally, I discuss my ongoing independent work on One-Time Programs, mixing quantum cryptography, error correcting codes and information theory

Une étape importante pour le développement des réseaux quantiques est de combiner les protocoles de cryptographie avec les mémoires quantiques afin d'établir des communications sécurisées où les informations peuvent être stockées et récupérées sur demande. Un cas d'utilisation possible de ces réseaux est d'effectuer des transactions authentifiées synchronisées par l'utilisation de mémoires. Cependant, les pertes et le bruit ajoutés par les dispositifs de stockage peuvent être exploités par des agents malveillants pour dissimuler leurs tentatives de fraude. Les contraintes pour opérer dans un régime sécurisé sont donc très exigeantes en termes d'efficacité et de fidélité de la mémoire. Cette thèse se concentre sur l'implémentation d'un ensemble d'atomes froids, utilisé en tant que mémoire quantique basée sur l'EIT, dans un protocole de cryptographie. Les ingrédients clés pour optimiser l'efficacité de stockage ainsi que la méthode employée pour atténuer les sources de décohérence sont détaillés. Ce travail représente la première démonstration du protocole cryptographique nommé "quatum money" incluant une étape intermédiaire de stockage, tirant parti de notre mémoire quantique hautement efficace et à faible bruit. L'étape suivante consisterait à multiplexer spatialement le nuage atomique afin de stocker toute la séquence de qubits aléatoires en une seule fois. Dans ce contexte, la capacité multimode de notre mémoire a été simulée numériquement en utilisant deux techniques différentes de multiplexage spatial
Combining cryptographic protocols with quantum memories is an important step for quantum network development in order to establish secure communications where information can be stored and retrieved on demand. One possible use case of these networks is to perform authenticated transactions synchronized by the use of memories. However, the losses and noise added by storage devices can be exploited by dishonest agents to hide their cheating attempts. The constraints to operate in a secure regime are thus very demanding in terms of memory efficiency and fidelity. This thesis focuses on the implementation of a cold-atomic ensemble used as an EIT-based quantum memory in a cryptographic protocol. The key ingredients to optimize the storage-and-retrieval efficiency and the method employed to mitigate the decoherence sources are detailed. This work reports the first demonstration of the unforgeable quantum money including an intermediate quantum memory layer, taking advantage of our highly-efficient and low-noise storage platform. The next step would be to spatially multiplex the atomic cloud in order to store the whole sequence of random qubits at once. In this scenario, the multimode capacity of our memory has been numerically simulated using two different spatial multiplexing techniques

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
This thesis stands at the interface between quantum theory and experiments, focusing on practical protocols that can be implemented using present-day technology. Our goal is to build a general framework for the design and implementation of quantum cryptographic schemes that will improve the safety of future telecommunication networks. In addition, this thesis aims to advance research on quantum physics and computer science, by improving our understanding of entanglement. The correlations of entangled states can not be reproduced by conventional means, allowing to perform tasks (eg teleportation and superdense coding) that are otherwise impossible. It is therefore of major importance to be able to check whether a quantum state is entangled. In this thesis, we show how to efficiently check whether a physical source can create multi-party entangled states and share them with many parties, some of which are dishonest and work with the source. This protocol could prove essential for quantum computation between suspicious parties and could also facilitate the secure delegation of tasks to powerful untrusted quantum servers. Finally, we study the link between game theory and quantum non-locality, in the context of Bayesian games. We examine how the shared entanglement helps players win a game with a higher probability than the conventional resources could achieve

Le premier protocole cryptographique basé sur les codes correcteurs d'erreurs a été proposé en 1978 par Robert McEliece. La cryptographie basée sur les codes est dite post-quantique car il n'existe pas à l'heure actuelle d'algorithme capable d'attaquer ce type de protocoles en temps polynomial, même en utilisant un ordinateur quantique, contrairement aux protocoles basés sur des problèmes de théorie des nombres. Toutefois, la sécurité du cryptosystème de McEliece ne repose pas uniquement sur des problèmes mathématiques. L'implantation, logicielle ou matérielle, a également un rôle très important pour sa sécurité et l'étude de celle-ci face aux attaques par canaux auxiliaires/cachés n'a débuté qu'en 2008. Des améliorations sont encore possibles. Dans cette thèse, nous proposons de nouvelles attaques sur le déchiffrement du cryptosystème de McEliece, utilisé avec les codes de Goppa classiques, ainsi que des contre-mesures correspondantes. Les attaques proposées sont des analyses de temps d'exécution ou de consommation d'énergie. Les contre-mesures associées reposent sur des propriétés mathématiques et algorithmiques. Nous montrons qu'il est essentiel de sécuriser l'algorithme de déchiffrement en le considérant dans son ensemble et non pas seulement étape par étape
The first cryptographic protocol based on error-correcting codes was proposed in 1978 by Robert McEliece. Cryptography based on codes is called post-quantum because until now, no algorithm able to attack this kind of protocols in polynomial time, even using a quantum computer, has been proposed. This is in contrast with protocols based on number theory problems like factorization of large numbers, for which efficient Shor's algorithm can be used on quantum computers. Nevertheless, the McEliece cryptosystem security is based not only on mathematical problems. Implementation (in software or hardware) is also very important for its security. Study of side-channel attacks against the McEliece cryptosystem have begun in 2008. Improvements can still be done. In this thesis, we propose new attacks against decryption in the McEliece cryptosystem, used with classical Goppa codes, including corresponding countermeasures. Proposed attacks are based on evaluation of execution time of the algorithm or its power consumption analysis. Associate countermeasures are based on mathematical and algorithmic properties of the underlying algorithm. We show that it is necessary to secure the decryption algorithm by considering it as a whole and not only step by step

Les preuves zero-knowledge sont un outil essentiel en cryptographie. Elles permettent de prouver une affirmation ou une connaissance, sans aucune fuite d’information sur les secrets utilisés. Ces preuves interactives, ou non-interactives, sont présentées avec plusieurs niveaux de sécurité. Elles seront, par la suite, utilisées dans de nombreux protocoles.

Afin d’authentifier son interlocuteur lors d’un échange de clé, plusieurs méthodes sont possibles, de la clé symétrique long-terme à la clé publique. Mais la plus pratique est l’utilisation d’un mot de passe commun. Néanmoins, la sécurité devient délicate à définir et à garantir. Ce chapitre présente tout cela en détails.