Mohammed Barhoush

Different flavors of quantum pseudorandomness have proven useful for various cryptographic applications, with the compelling feature that these primitives are potentially weaker than post-quantum one-way functions. Ananth, Lin, and Yuen (2023) have shown that logarithmic pseudorandom states can be used to construct a pseudo-deterministic PRG: informally, for a fixed seed, the output is the same with 1 − 1/poly probability. In this work, we introduce new definitions for ⊥-PRG and ⊥-PRF. The correctness guarantees are that, for a fixed seed, except with negligible probability, the output is either the same (with probability 1 − 1/poly) or recognizable abort, denoted ⊥. Our approach admits a natural definition of multi-time PRG security, as well as the adaptive security of a PRF. We construct a ⊥-PRG from any pseudo-deterministic PRG and, from that, a ⊥-PRF. Even though most mini-crypt primitives, such as symmetric key encryption, commitments, MAC, and length-restricted one-time digital signatures, have been shown based on various quantum pseudorandomness assumptions, digital signatures remained elusive. Our main application is a (quantum) digital signature scheme with classical public keys and signatures, thereby addressing a previously unresolved question posed in Morimae and Yamakawa’s work (Crypto, 2022). Additionally, we construct CPA secure public-key encryption with tamper-resilient quantum public keys.

The bounded quantum storage model aims to achieve security against computationally unbounded adversaries that are restricted only with respect to their quantum memories. In this work, we provide everlasting and information-theoretic secure constructions in this model for the following powerful primitives: (1) CCA1-secure symmetric key encryption, message-authentication, and one-time programs. These schemes require no quantum memory for the honest user, while they can be made secure against adversaries with arbitrarily large memories by increasing the transmission length sufficiently. (2) CCA1-secure asymmetric key encryption, encryption tokens, signatures, and signature tokens. These schemes are secure against adversaries with roughly $e^{\sqrt{m}}$ quantum memory where $m$ is the quantum memory required for the honest user. All of the constructions additionally satisfy notions of disappearing and unclonable security.