International Association
for Cryptologic Research

We investigate two natural relaxations of quantum cryptographic primitives. The first involves quantum input sampling, where inputs are generated by a quantum algorithm rather than sampled uniformly at random. Applying this to pseudorandom generators ($\textsf{PRG}$s) and pseudorandom states ($\textsf{PRS}$s), leads to the notions denoted as $\textsf{PRG}^{\textsf{qs}}$ and $\textsf{PRS}^{\textsf{qs}}$, respectively. The second relaxation, $\bot$-pseudodeterminism, relaxes the determinism requirement by allowing the output to be a special symbol $\bot$ on an inverse-polynomial fraction of inputs. We demonstrate an equivalence between bounded-query logarithmic-size $\textsf{PRS}^{\textsf{qs}}$, logarithmic-size $\textsf{PRS}^{\textsf{qs}}$, and $\textsf{PRG}^{\textsf{qs}}$. Moreover, we establish that $\textsf{PRG}^{\textsf{qs}}$ can be constructed from $\bot$-\textsf{PRG}s, which in turn were built from logarithmic-size $\textsf{PRS}$. Interestingly, these relations remain unknown in the uniform key setting. To further justify these relaxed models, we present black-box separations. Our results suggest that $\bot$-pseudodeterministic primitives may be weaker than their deterministic counterparts, and that primitives based on quantum input sampling may be inherently weaker than those using uniform sampling. Together, these results provide numerous new insights into the structure and hierarchy of primitives within MicroCrypt.

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.