Paper 2026/2002
Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States
, Korea Advanced Institute of Science and TechnologyAbstract
Quantum computation gives rise to new pseudorandom primitives for states and unitaries, including pseudorandom state generators (PRSGs), pseudorandom function-like state generators (PRFSGs), and pseudorandom unitaries (PRUs). In this paper, we show a full unitary oracle separation between PRFSGs and PRUs. The separation holds between the strongest state notion and the weakest unitary notion: even adaptively secure, quantum-accessible PRFSGs do not imply non-adaptively secure, forward-only PRUs, even when their implementations are allowed to be non-unitary and use an arbitrary number of ancillary qubits. This reveals a fundamental distinction between pseudorandomness for quantum states and for quantum unitaries. Our main technical idea is to view a candidate PRU construction with access to state generation oracles as a map from the underlying oracle states to implemented unitaries, and to study the derivatives of this map. These derivatives are inherently low rank, and we exploit this low-rank structure to distinguish the resulting unitaries from truly random ones. We believe this differential perspective may be useful for studying other structural questions about quantum states and unitaries.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- Quantum PseudorandomnessQuantum CryptographyPseudorandom UnitariesPseudorandom Function-like State
- Contact author(s)
- minkihhan @ kaist ac kr
- History
- 2026-09-14: approved
- 2026-09-13: received
- See all versions
- Short URL
- https://ia.cr/2026/2002
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/2002,
author = {Minki Hhan},
title = {Derivatives of Quantum Randomness: Separating Pseudorandom Unitaries from Pseudorandom (Function-like) States},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2002},
year = {2026},
url = {https://eprint.iacr.org/2026/2002}
}
