Supervision : Damien VERGNAUD

Co-supervision : Alex BREDARIOL GRILO

Impact of quantum computer on Impagliazzo's five worlds

The main goal in our project is to explore novel consequences that quantum computing could bring to Impagliazzo's five worlds, specially its impact on cryptography. Despite the impressive success of quantum computation/cryptography, we remark that progress on this line has been very limited. Examples of questions that could be explored by the PhD candidate are: Constant-round ZK proofs from OWF. There is strong evidence that zero-knowledge proofs (a fundamental cryptographic primitive) cannot be implemented in constant-round classically in the plain mode, i.e. without any trusted help (Katz'08). However, these no-go results rely on complexity theoretical assumptions that do not quantize. Thus, a natural open question that could be explore in this PhD project is the (in)feasibility of constant-round quantum zero-knowledge proofs (ideally from one- way functions). This could clarify which type of advantage quantum resources can provide on the construction of cryptographic primitives. Role of quantum obfuscation in quantum cryptography. In the classical world, the concept of indistinguishable obfuscation (iO), which asks that the ofuscation of two programs with the same functionality cannot be distinguished, has been shown to be a very strong primitive that can enable the implementation of several cryptographic primitives which are not known to exist otherwise. To stress its usefulness, iO is frequently called "crypto-complete" in the classical scenario. Such a strong functionality comes of course with a cost: for decades the existence of secure iO schemes was elusive, until a very recent result of Jain, Lin and Sahai, which constructs iO from well-founded cryptographic assumptions. The study of obfuscation in the quantum setting, specially its consequences, has been very limited. In particular, a direction that could be pursued in this PhD project would be to study the feasibility of strong quantum functionalities from quantum iO. Lower bounds on quantum cryptographic protocols. Shoup’97 showed that in a "generic group" model, it is impossible to solve the discrete logarithm problem (or Diffie-Hellman) of a group of prime order p using O(sqrt(p)) group operations. Shor's polynomial algorithm for discrete-log directly implies that such a lower bound does not hold in the quantum setting. One potential direction for this PhD project would be to study if such lower bounds on the computational complexity for quantum algorithms can be proven for other generic mathematical structures, for example the Couveignes hard homogeneous spaces (based on group actions) underlying the cryptographic constructions based on elliptic curves isogenies, a cryptographic assumption that has resisted to quantum attacks (so far)

2023-2024 Publications

• 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)