In this thesis, we study both classical and quantum cryptography within idealized quantum models. Previous work has shown that quantum resources can be used to construct cryptographic tasks that are proven or conjectured to be impossible in the classical setting. Here, we first prove lower bounds on the efficiency of any quantum algorithm that finds a subset-cover of a random function, a problem that has been conjectured to be hard for assessing the security of the post-quantum digital signature scheme SPHINCS+. Next, we extend existing impossibility results for constructing public-key encryption schemes in the quantum random oracle model by showing that a more general type of public-key encryption does not exist in this model. We then study quantum assumptions for cryptography that appear weaker than one-way functions, namely quantum pseudorandomness, and its relationship to quantum public key encryption and signature schemes, both clarifying and improving upon prior constructions and impossibility proofs. Finally, we establish the importance of the size of pseudorandomness by proving that quantum pseudorandomness cannot be shrunk, and we make progress toward showing that it cannot be amplified.
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)