arXiv:2609.40301
Need for Coherent Access in Constructing Quantum Cryptography
Minki Hhan, Changhun Oh, Vaughn Sohn
Abstract
We construct quantum oracles relative to which quantum-secure one-way functions (OWFs) exist but pseudorandom states (PRSs) with superlogarithmic output length do not. At first glance, this appears to contradict the known black-box constructions of PRS generators from quantum-secure OWFs. The distinction lies in the access model to the oracles; our oracle separation uses \emph{classical-accessible} random oracles that can be accessed only classically even by quantum algorithms. In fact, our impossibility of PRSs applies to \emph{any} classically accessible classical oracle in place of the random oracle, while keeping the other oracle component unchanged, showing the need for coherent access in constructing PRSs. We further show that logarithmic output length pseudorandom function-like states (PRFSs) exist relative to our oracles, giving an oracle separation between classically accessible logarithmic length PRFSs and superlogarithmic length PRSs. This shows that fully black-box PRS length extension from logarithmic to superlogarithmic output length must use coherent access to the underlying short PRS.
AI Summary
Can quantum-secure one-way functions yield pseudorandom quantum states without coherent access to the underlying classical primitive? This paper studies that question through an oracle separation, distinguishing classical-query access from the coherent access used in known OWF-to-PRS constructions. It constructs an oracle $\mathcal O=(\mathcal R,\mathsf{QPSPACE})$, where $\mathcal R$ measures classical-function query inputs before returning answers, and $\mathsf{QPSPACE}$ executes exponentially long, polynomial-width oracle-free unitary circuits. With probability one over the random functions, quantum-secure OWFs exist relative to $\mathcal O$, together with standard classical minicrypt primitives. However, for every choice of those functions, no PRS generator with output length $m(\lambda)=\omega(\log\lambda)$ exists—even allowing mixed outputs, adaptive queries, and polynomially many ancillas. The PRS impossibility also holds when the random-function component is replaced by any classically accessible classical oracle. The distinguisher combines purity testing with enumeration of oracle-free circuits reproducing postselected execution branches. Fixed-point amplitude amplification boosts useful branches, and a quantum OR test checks their overlap with the challenge. Using $3L$ copies for a generator-dependent polynomial $L\ge\lambda$, it achieves advantage at least $1/28-2^{-\lambda}$ with one $\mathsf{QPSPACE}$ call; Haar-moment bounds control false positives. Logarithmic-output, classically accessible PRFSs also exist in this oracle world, ruling out fully black-box extension to superlogarithmic PRSs without coherent access. These are access-model-specific oracle results, not standard-model impossibilities; the paper notes that classical-accessible and coherent-access oracle separations are not directly comparable.
OpenAI GPT-6 Astra was used to prepare an initial written draft of the proofs based on the authors' arguments.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.