BOUAZIZ ERMANN Samuel
Team : ALMASTY
Arrival date : 08/28/2021
 Sorbonne Université  LIP6
Boîte courrier 169
Couloir 2425, Étage 4, Bureau 413
4 place Jussieu
75252 PARIS CEDEX 05
FRANCE
Tel: +33 1 44 27 47 28, Samuel.BouazizErmann (at) nulllip6.fr
https://lip6.fr/Samuel.BouazizErmann
Supervision : Damien VERGNAUD
Cosupervision : 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: Constantround ZK proofs from OWF. There is strong evidence that zeroknowledge proofs (a fundamental cryptographic primitive) cannot be implemented in constantround classically in the plain mode, i.e. without any trusted help (Katz'08). However, these nogo 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 constantround quantum zeroknowledge 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 "cryptocomplete" 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 wellfounded 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 DiffieHellman) of a group of prime order p using O(sqrt(p)) group operations. Shor's polynomial algorithm for discretelog 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 Publications

2023
 S. Bouaziz‑‑Ermann, A. Bredariol Grilo, D. Vergnaud, Q.‑H. Vu : “Towards the Impossibility of Quantum Public Key Encryption with Classical Keys from OneWay Functions”, (2023)
 S. Bouaziz‑‑Ermann, A. Bredariol Grilo, D. Vergnaud : “Quantum security of subset cover problems”, 4^{th} Conference on InformationTheoretic Cryptography (ITC 2023), vol. 267, Leibniz International Proceedings in Informatics (LIPIcs), Aahrus, Denmark, pp. 9:19:17, (Schloss Dagstuhl  LeibnizZentrum fur Informatik), (ISBN: 9783959772716) (2023)