Paper 2025/285

MicroCrypt Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations

Abstract

We investigate two natural relaxations of quantum cryptographic assumptions. First, we examine primitives such as pseudorandom generators (${PRG}$s) and pseudorandom states (${PRS}$s), extended with quantum input sampling, which we term ${PRG}^{qs}$ and ${PRS}^{qs}$. In these primitives, the input is sampled via a quantum algorithm rather than uniformly at random. The second relaxation, $\bot$-pseudodeterminism, allows the generator to output $\bot$ on an inverse-polynomial fraction of inputs. We demonstrate an equivalence between (bounded-query) logarithmic-sized ${PRS}^{qs}$, logarithmic-sized ${PRS}^{qs}$, and ${PRG}^{qs}$. Notably, such an equivalence remains unknown for the uniform key sampling versions of these primitives. Furthermore, we establish that ${PRG}^{qs}$ can be constructed from $\bot$-pseudodeterministic ${PRG}$s ($\bot{-PRG}$s). To further justify our exploration, we present two separation results. First, we examine the relationship between $\bot$-pseudodeterministic notions and their deterministic counterparts. We show that there does not exist a black-box construction of a one-way state generator $({OWSG})$ from a $\bot{-PRG}$, indicating that $\bot$-pseudodeterministic primitives may be inherently weaker than their deterministic counterparts. Second, we explore the distinction between quantum and uniform input sampling. We prove that there does not exist a black-box construction of a $\bot$-psuedodeterministic ${OWSG}$ from a ${PRF}^{qs}$, suggesting that primitives relying on quantum input sampling may be weaker than those using traditional uniform sampling. Given the broad cryptographic applicability of ${PRF}^{qs}$s and $\bot{-PRG}$s, these separation results yield numerous new insights into the hierarchy of primitives within MicroCrypt.