Direction de recherche : Damien VERGNAUD

Co-encadrement : Alex BREDARIOL GRILO

L'impact des ordinateurs quantiques sur les cinq mondes d'Impagliazzo

L'objectif principal de ce projet de thèse est d'explorer les nouvelles conséquences sur les cinq mondes d'Impagliazzo que peuvent apporter les ordinateurs quantiques, et plus particulièrement leurs impacts sur la cryptographie. Malgré le succès impressionnant des ordinateurs quantiques et de la cryptographie quantique, on remarque que les progrès sur cette ligne ont été très limités. Voici des exemples de questions qui peuvent être explorées par le doctorant : Preuve à divulgation nulle de connaissance à round constant à partir de fonctions à sens unique. Il y a de fortes indications que les preuves à divulgation nulles de connaissance (une primitive cryptographique fondamentale) ne peuvent pas être implémentée avec un nombre constant de round classiquement dans le modèle standard, c'est-à-dire sans aide de confiance (Katz'08). Cependant, ces résultats d'impossibilité reposent sur des hypothèses de complexité classique qui ne s'adaptent pas au paradigme quantique. Ainsi, une question naturelle qui peut être explorée dans ce projet de thèse et la faisabilité de preuve à divulgation nulle de connaissance quantique avec un nombre constant de round (idéalement à partie de fonctions à sens unique). Ceci pourrait permettre de clarifier quel type d'avantages les ressources quantiques peuvent apporter pour la construction de primitives cryptographiques. Le rôle de l'offuscation quantique pour la cryptographie quantique. Dans le paradigme classique, il a été démontré que le concept d'offuscation indistinguable (iO), qui nécessite que l'offuscation de deux programmes avec la même fonctionnalité ne puisse pas être distinguée est une primitive très puissante qui permet l'implémentation de plusieurs primitives cryptographiques que nous ne savons pas implémentable autrement. Pour insister sur son utilité, iO est fréquemment appelée "crypto-complet" dans le cadre classique. Une fonctionnalité si puissante vient évidemment avec un coût : depuis des dizaines d'années l'existence de schéma iO sécurisé était évasif, jusqu'à un résultat très récent de Jain, Lin et Sahai, qui construit iO à partir d'hypothèses cryptographiques bien connues. L'étude de l'offuscation dans le paradigme quantique, et en particulier ses conséquences, est très limitée. En particulier, une direction qui peut être poursuite par le doctorant est l'étude de la faisabilité de fortes fonctionnalités quantiques à partir d'iO quantique. Bornes inférieures sur des protocoles cryptographiques quantiques. Shoup'97 a démontré que dans un modèle de "groupe générique", il est impossible de résoudre le problème du logarithme discret (ou Diffie-Hellman) d'un groupe d'ordre premier p en utilisant O(racine(p)) opérations de groupe. L'algorithme polynomial de Shor pour le logarithme discret implique directement que ces bornes inférieures ne tiennent pas dans le paradigme quantique. Une direction potentielle de ce projet de thèse serait d'étudier si ces bornes inférieures sur la complexité calculatoire pour des algorithmes quantiques peuvent être prouvées pour d'autres structures mathématiques génériques. Par exemple les espaces homogènes durs de Couveignes (fondés sur des actions de groupes) sur lesquels reposent la constructions cryptographique fondées sur les courbes elliptiques isogènes, une hypothèse cryptographique qui a résistée aux attaques quantiques (pour l'instant)

Publications 2023-2024

• 2024
  • S. Bouaziz‑‑Ermann, A. Bredariol Grilo, D. Vergnaud, Q.‑H. Vu : “Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from One-Way Functions”, IACR Communications in Cryptology, (International Association for Cryptologic Research (IACR)) (2024)
• 2023
  • S. Bouaziz‑‑Ermann, A. Bredariol Grilo, D. Vergnaud : “Quantum security of subset cover problems”, 4^th Conference on Information-Theoretic Cryptography (ITC 2023), vol. 267, Leibniz International Proceedings in Informatics (LIPIcs), Aahrus, Denmark, pp. 9:1-9:17, (Schloss Dagstuhl -- Leibniz-Zentrum fur Informatik), (ISBN: 978-3-95977-271-6) (2023)