Facing and Exploiting the Quantum Wave in Computing: New Security Definitions and Cryptographic Constructions
Affronter et exploiter la vague quantique en informatique : nouvelles définitions de la sécurité et constructions cryptographiques
Résumé
Modern cryptography has a major foe on the horizon: the inevitable rise of quantum computers. However, the same computing power will also unlock solutions to cryptographic tasks that are simply impossible to achieve with the current technology. This thesis sets foot in a ubiquitous quantum world, where everyone will be running quantum computers, with two main contributions.
Firstly, we put forth new security models and security analyses for two cryptographic primitives: encryption and non-interactive zero-knowledge proofs. Classical security definitions of these primitives inherently require the ability to record and compare classical strings. However, the tasks of recording and comparing are highly non-trivial in the quantum setting, due to the quantum uncertainty principle. We propose two different ways to overcome this recording barrier. Our security notions are the first to fully capture quantum attacks in which the codebreakers can interact with the end-users over quantum channels.
Secondly, we show that the availability of quantum computers turns out to be also the advantage of codemakers, even when the end-users only use classical communication. In particular, we exhibit an interactive protocol between a classical Alice and a quantum Bob which allows Alice to send a hidden unclonable quantum state to Bob through classical channels. Furthermore, the constructed unclonable quantum state establishes a strong monogamy-of-entanglement property, which describes the limitations on the strength of quantum multipartite correlations. We further apply our protocol to quantum copy-protection and give the first semi-quantum copy-protection schemes.
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.
Origine : Fichiers produits par l'(les) auteur(s)