Quantum oracles show limits of classical access in cryptography
Need for Coherent Access in Constructing Quantum Cryptography
Cryptography and Security
Summary
This paper examines how quantum computers can access special black-box tools called oracles differently. The authors show that if quantum programs can only interact with these oracles in a 'classical' way—without using quantum superposition—the creation of certain secure quantum states called pseudorandom states is impossible. However, some simpler forms of these states still exist under these restrictions. This reveals that quantum programs need a more 'coherent' or quantum way of accessing oracles to build strong quantum cryptographic tools.
What this means in practice
- •For quantum software developers: Understand when quantum algorithms cannot build certain secure states if they are restricted to classical queries to subroutines, aiding secure quantum protocol design.
- •For cryptography engineers: Use knowledge about oracle access requirements to avoid flawed constructions of quantum pseudorandom states in designing quantum-resistant cryptographic schemes.
A theory result. No direct application yet.
Authors
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.