Cryptographic Primitives in Quantum Idealized Models

Congratulations Dr.Bouaziz Ermann !!

Abstract

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.