Description
Date depot: 10 septembre 2021
Titre: Impact of quantum computer on Impagliazzo's five worlds
Directeur de thèse:
Damien VERGNAUD (LIP6)
Encadrant :
Alex BREDARIOL GRILO (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Calcul arithmétique et formel, codage et cryptologie
Resumé: Depuis ses débuts, l'informatique quantique a eu des conséquences importantes sur la cryptographie. D'une part, des ordinateurs quantiques pourraient être utilisés pour casser des cryptosystèmes largement utilisés, notamment grâce au célèbre algorithme de Shor pour la factorisation des entiers. D'autre part, les ressources quantiques ont également été utilisées pour réaliser des tâches cryptographiques autrement impossibles, par exemple la monnaie quantique, la mise en accord de clés privées ou la génération d'aléa certifié. Ces primitives peuvent être construites dans le monde quantique inconditionnellement, c'est-à-dire sans avoir besoin d'imposer une hypothèse de complexité calculatoire aux adversaires.
En 1995, R. Impagliazzo a défini cinq mondes liés à des notions de complexité et de cryptographie : Algorithmica, dans lequel P = NP ; Heuristica, dans lequel les problèmes de la classe NP sont difficiles dans le pire des cas mais facile en moyenne ; Pessiland, dans lequel les problèmes de la classe NP sont difficile en moyenne mais il n'existe pas de fonction à sens-unique ; Minicrypt, dans lequel les fonctions à sens-unique existent et Cryptomania, dans lequel le chiffrement à clé publique existe. L'objectif principal de ce PRD est d'explorer les nouvelles conséquences que l'informatique quantique pourrait apporter aux cinq mondes d'Impagliazzo, en particulier son impact sur la cryptographie. Malgré le succès impressionnant de l'informatique et la cryptographie quantique, nous constatons que les progrès dans ce domaine ont été très limités.
Voici quelques exemples de questions qui pourraient être explorées par le doctorant :
- Les preuves à divulgation nulle de connaissance en nombre de tours constant à partir de fonction à sens-unique.
- Le rôle de l'obfuscation quantique dans la cryptographie quantique.
- Les bornes inférieures de complexité des protocoles de cryptographie quantique
Résumé dans une autre langue: Since its early stages, quantum computing has had important implications for cryptography. On the one hand, quantum computers could be used to break widely used cryptosystems,given the celebrated Shor's famous algorithm for integer factorization. On the other hand, quantum resources have also been used to perform otherwise impossible cryptographic tasks, such as quantum money, private key agreement, or certified randomness generation. These primitives can be constructed in the quantum world unconditionally, i.e., without the need to impose a computational complexity assumption on adversaries.
In 1995, R. Impagliazzo defined five worlds related to notions of complexity and cryptography: Algorithmica, in which P = NP; Heuristica, in which problems of the class NP are hard in the worst case but easy on average; Pessiland, in which problems of the class NP are hard on average but there is no one-way function; Minicrypt, in which one-way functions exist and Cryptomania, in which public key encryption exists. The main objective of this PRD is to explore the new consequences that quantum computing could bring to Impagliazzo's five worlds, in particular its impact on cryptography. Despite the impressive success of quantum computing and cryptography, we note that progress in this area has been very limited.
Examples of questions that could be explored by the PhD student include:
- Zero-disclosure proofs of constant-round knowledge from one-way functions.
- The role of quantum obfuscation in quantum cryptography.
- Lower bounds on the complexity of quantum cryptographic protocols
Doctorant.e: Bouaziz--Ermann Samuel