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, $\mathrm{\perp }$-pseudodeterminism, allows the generator to output $\mathrm{\perp }$ on an inverse-polynomial fraction of inputs. We demonstrate an equivalence between (bounded-query) logarithmic-sized $$, logarithmic-sized $$, and $$. Notably, such an equivalence remains unknown for the uniform key sampling versions of these primitives. Furthermore, we establish that $$ can be constructed from $$-pseudodeterministic $$s ($$s). To further justify our exploration, we present two separation results. First, we examine the relationship between $$-pseudodeterministic notions and their deterministic counterparts. We show that there does not exist a black-box construction of a one-way state generator $$ from a $$, indicating that $$-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 $$-psuedodeterministic $$ from a $$, suggesting that primitives relying on quantum input sampling may be weaker than those using traditional uniform sampling. Given the broad cryptographic applicability of $$s and $$s, these separation results yield numerous new insights into the hierarchy of primitives within MicroCrypt.