Source-linked AI summary
Need for Coherent Access in Constructing Quantum Cryptography
Minki Hhan, Changhun Oh, Vaughn Sohn
TL;DR
The paper asks whether pseudorandom states can be constructed from classical primitives without coherent access. It constructs an oracle separation using classically accessible access, showing that quantum-secure OWFs and logarithmic-length PRFSs can exist while superlogarithmic-length PRSs do not.
Problem
Known OWF-to-PRS constructions rely heavily on coherent access, raising whether quantum cryptography can be constructed from classical primitives without it.
Source: §1 · p. 3Method
The paper constructs a quantum-channel oracle separation using classically accessible random-oracle access, and extends the PRS impossibility to any classically accessible classical oracle with the other component unchanged.
Source: §1.1 · pp. 3–4Results
A quantum channel oracle supports quantum-secure OWFs and log-length PRFSs, but not PRSs with output length m(λ) = ω(log λ).
Source: §1.1 · pp. 3–4Takeaways & Limitations
In this oracle setting, fully black-box PRS construction from OWFs and length extension from short PRS require coherent access.
Source: §1.1 · pp. 3–4The separation uses classically accessible oracles, which are not generally directly comparable to unitary or quantum-accessible oracle models.
Source: §1.1 · p. 4
Abstract
from arXiv · showhide
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.
1 Introduction
The paper separates quantum-secure one-way functions from superlogarithmic-length pseudorandom states in an oracle model where quantum algorithms can access the random oracle only classically. Its results show that coherent access is essential to the studied constructions of pseudorandom states, while short pseudorandom function-like states and classical cryptographic primitives can still exist.
1 Introduction
- Known OWF-to-PRS constructions rely heavily on coherent access, motivating whether quantum cryptography can be built from classical primitives without it.The paper notes that coherent evaluation can require preserving quantum coherence, extra ancillas, and uncomputation time.Source: §1 · p. 3
1.1 Our results
- A quantum channel oracle supports quantum-secure OWFs but no PRS with output length m(λ) = ω(log λ); with the same oracles, classical-accessible log-length PRFSs exist.The impossibility also holds for slightly mixed outputs and for any classically accessible classical oracle replacing the random oracle while the other oracle component is unchanged.Source: §1.1 · pp. 3–4
1.2 Technical overview
- The oracle combines a classically accessible random oracle with an independent QPSPACE oracle, then uses purity and candidate-branch overlap tests to distinguish generated states.The attack enumerates possible classical oracle answers to form oracle-free candidate circuits and combines their overlap tests with a quantum OR test.Source: §1.2 · p. 5, §1.2.2 · pp. 6–7
1.2.1 Construction of OWFs
- Classical queries to the random oracle implement OWFs because polynomially many queries have negligible inversion success, even with access to the independent QPSPACE oracle.The random-function inversion bound holds regardless of computation between queries.Source: §1.2.1 · p. 5
1.2.2 Oracle separation of PRS from OWFs
- For mixed generator outputs, low purity is detected by SWAP tests; otherwise a sufficiently overlapping pure branch supplies a candidate for an OR test that rejects Haar-random states when m(λ) = ω(log λ).Fixed-point amplitude amplification addresses exponentially small branch-preparation probabilities, while enumerating classical oracle answers removes the random oracle from candidate circuits.Source: §1.2.2 · pp. 6–7
2 Preliminaries
This section establishes notation and defines the classical and quantum cryptographic primitives used in the paper. It also recalls quantum tests used later to distinguish or analyze states.
2 Preliminaries
- The paper defines negligible functions, uniform sampling notation, and shorthand for functions of the security parameter.A function is negligible if it is eventually bounded by the reciprocal of every positive polynomial.Source: §2 · p. 7
2.1 Cryptographic primitives
- Classical primitives include one-way functions, pseudorandom generators, and pseudorandom functions, with the latter defined here for classical queries by quantum adversaries.The section also specifies security requirements for secret-key encryption, message authentication codes, and interactive bit commitments.Source: §2.1 · pp. 8–9
- Pseudorandom states are keyed quantum states whose polynomially many copies are computationally indistinguishable from the same number of Haar-random states.The paper allows the generator output to be mixed and considers superlogarithmic output length by default.Source: §2.1 · p. 9
2.2 Quantum property tests
- The SWAP test compares states through their overlap, while the purity test is its special case with both inputs equal.The quantum OR test combines candidate measurements using one copy of the input state rather than requiring a separate copy for each candidate.Source: §2.2 · p. 9
3 Oracle Model
The oracle model distinguishes coherent access from access that measures query inputs, and combines a classical-accessible random oracle with a QPSPACE oracle. The latter can apply oracle-free quantum circuits specified through bounded-time commands.
3.1 Oracles for quantum algorithms
- Quantum operation oracles may expose a unitary and its inverse, a unitary alone, an isometry, or a channel; a channel traces out its environment and can provide less access than its unitary extension.The channel interface returns only the reduced output state.Source: §3.1 · p. 10
- Coherent access to a classical function evaluates it unitarily, whereas the classical-accessible interface measures the query register and destroys coherence between distinct inputs.The response register is XORed with the function value at the measured input.Source: §3.1 · p. 10
3.2 Our oracle
- The oracle O consists of a classical-accessible random oracle R and a QPSPACE oracle.For each security parameter, R samples a uniform function once and keeps it fixed; QPSPACE measures command registers and runs a specified oracle-free machine subject to a time bound.Source: §3.2 · pp. 10–11
- The QPSPACE interface applies a valid oracle-free unitary circuit to its data register when the specified machine outputs one within the bound, and otherwise leaves the data unchanged and flips the abort qubit.Because the time bound is binary encoded, a polynomial-length command can specify exponentially many gates.Source: §3.2 · p. 11
4 Constructions of OWFs
The construction uses the classical-accessible random function as an OWF and proves it remains hard to invert for quantum polynomial-time adversaries with access to the full oracle. The same oracle world supports standard classical primitives.
4 Constructions of OWFs
- With probability 1 over the random functions, the induced family is a quantum-secure OWF relative to O.The proof concludes that the family is classically computable and quantum-secure against every QPT adversary, including access to QPSPACE.Source: §4 · pp. 11, 13
- The construction sets fλ(x) = Rλ(x), so one classical query to R computes the function.The inversion proof treats the adversary’s output as a hypothetical final query and bounds success by considering the first query that finds a preimage.Source: §4 · pp. 11–12
- The proof bounds each attempt after a failure history by separating the case where the query is the planted input from the case where it is another preimage.Repeated queries cannot succeed after the failure history; fresh inputs retain uniform function values.Source: §4 · p. 12
- Relative to O, the random functions also yield quantum-secure PRGs, PRFs with classical queries, secure encryption and MACs, and statistically binding, computationally hiding bit commitments.The constructions use classical evaluations, and their security reductions preserve the adversary’s prescribed access to O.Source: §4 · p. 13
- These classical primitives can exist in an oracle world without PRS of output length ω(log λ).This follows from the classical-primitive existence result together with the PRS impossibility result.Source: §4 · p. 13
5 Oracle Separation of PRS from OWFs
The section proves that no PRS with superlogarithmic output length exists relative to the oracle, for every choice of the random functions. Its attack reduces mixed generator outputs to branch candidates, amplifies them, and tests them against the generator’s outputs.
5.1 Constructing an oracle-free branch
- Mixed outputs split into low-purity states detectable by purity tests and near-pure states containing a sufficiently likely, high-overlap branch.The branch can be represented by an oracle-free unitary that reproduces its probability and output state upon postselection.Source: §5 · p. 14, §5.1 · pp. 14–15
5.2 Amplified candidate states for OR test
- Fixed-point amplification raises a rare branch’s preparation probability until its candidate projector satisfies the quantum OR lemma’s completeness condition.For the guaranteed branch, the initial success probability is at least 2^-L−1; the π/3 construction is used despite not achieving ordinary amplitude amplification’s query scaling.Source: §5.2 · pp. 16–17
5.3 The adversary and its analysis
- A QPT algorithm can implement an adversary distinguishing PRS outputs from Haar-random states with a single QPSPACE query, and the adversary’s acceptance probability is at least 1/28.Source: §5.3 · pp. 17, 19
- At least 1/28 − 2^-λ distinguishing advantage rules out every PRS generator with output length ω(log λ), for every choice of R.The adversary distinguishes generator outputs from Haar-random states.Source: §5 · p. 14, §5.3 · p. 20