International Association
for Cryptologic Research

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. Notably, 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 $\botPRG$ and $\botPRF$. 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 $\bot$. Our approach admits a natural definition of multi-time $\PRG$ security, as well as the adaptive security of a $\PRF$. We construct a $\botPRG$ from any pseudo-deterministic $\PRG$ and, from that, a $\botPRF$. While many Minicrypt primitives--such as symmetric encryption, commitments, MACs, and length-restricted one-time digital signatures--have been realized from quantum pseudorandomness assumptions, constructing full digital signatures remained an open challenge, and was explicitly posed as an open question by Morimae and Yamakawa (Crypto 2022). We resolve this by presenting the first (quantum) digital signature scheme with classical public keys and signatures from logarithmic pseudorandom states, utilizing our construction of $\botPRF$s. Additionally, we construct CPA secure public-key encryption with tamper-resilient quantum public keys. Combined with a recent work of Barhoush, Nishimaki, and Yamakawa (2025), our results demonstrate that these applications can be realized under assumptions that are separated from quantum evaluatable one-way functions.