Lior Ozer

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.