Security in the Presence of Quantum Adversaries

With the looming threat of large-scale quantum computers, a fair portion of recent cryptographic research has focused on examining cryptographic primitives from the perspective of a quantum adversary. Shor's 1994 result revealed that quantum computers can efficiently solve the discrete logarithm and factorization problems, the foundation of public-key cryptography's hardness assumptions. As a response, the field of post-quantum cryptography has emerged, aiming to redesign classical cryptographic primitives to maintain security against quantum adversaries.Conversely, quantum computation presents new opportunities for cryptographic design. It may be possible to construct cryptographic primitives designed specifically for quantum parties, relying on weaker assumptions compared to classical cryptography or even eliminating the need for any computational assumptions altogether. This has opened up exciting possibilities for exploring quantum-enhanced cryptographic schemes.In this thesis, we delve into both aspects: classical cryptography guaranteeing security against quantum adversaries and the potential opportunities presented by cryptographic primitives harnessing quantum computation. Throughout the first part of the thesis, we focus on post-quantum signature schemes. We examine signature schemes within the Minicrypt realm, built on the MPC-in-the-head framework and symmetric-key primitives. The results we present demonstrate that the security level of these schemes is influenced by the multiplication complexity of the underlying symmetric-key cipher. We specifically analyse the PICNIC signature scheme, instantiated with the LowMC block cipher family, and establish the importance of maintaining a sufficient round complexity in the block cipher to ensure security.The second part of the thesis focuses on cryptographic primitives specifically designed for parties utilizing quantum computation. We thoroughly explore the concept of public-key encryption (PKE) in the quantum domain and tackle the question of whether it is feasible to construct PKE schemes using assumptions weaker than those required in classical settings. We demonstrate that it is indeed possible to construct a quantum PKE scheme by relying solely on the existence of one-way functions or potentially weaker assumptions.Additionally, we explore the utilization of self-testing techniques from quantum mechanics in the field of learning theory. We focus on the challenge of constructing classifiers that exhibit robustness against test examples drawn from arbitrary distributions, including adversarially chosen examples. We showcase the application of self-testing techniques to offer cryptographic guarantees for such tasks within a quantum learning model.