Paper 2025/285

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

Mohammed Barhoush
Ryo Nishimaki, NTT (Japan)
Takashi Yamakawa, NTT (Japan)
Abstract

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 (PRGs) and pseudorandom states (PRSs), leads to the notions denoted as PRGqs and PRSqs, respectively. The second relaxation, -pseudodeterminism, relaxes the determinism requirement by allowing the output to be a special symbol on an inverse-polynomial fraction of inputs. We demonstrate an equivalence between bounded-query logarithmic-size , logarithmic-size , and . Moreover, we establish that can be constructed from -s, which in turn were built from logarithmic-size . 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 -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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Quantum CryptographyPseudorandom StatesPseudodeterminismBlack-Box Separation
Contact author(s)
mohammed barhoush @ umontreal ca
ryo nishimaki @ ntt com
takashi yamakawa @ ntt com
History
2025-05-20: last of 2 revisions
2025-02-19: received
See all versions
Short URL
https://ia.cr/2025/285
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/285,
      author = {Mohammed Barhoush and Ryo Nishimaki and Takashi Yamakawa},
      title = {{MicroCrypt} Assumptions with Quantum Input Sampling and Pseudodeterminism: Constructions and Separations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/285},
      year = {2025},
      url = {https://eprint.iacr.org/2025/285}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.