arXiv:2609.32603
Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model
Boyang Chen, Tianren Liu, Luojian Wei
Abstract
Quantum information enables many cryptographic primitives that are impossible in the classical world. A line of works has developed cryptographic protocol under the assumption that quantum adversaries are restricted to noisy intermediate-scale quantum (NISQ) computing power, enabling strong one-time functionalities. But the advent of early fault-tolerant quantum computers eras will allow deeper logical quantum circuits, calling into questions the applicability of these NISQ-based assumptions. In this work, we adapt the classically accessible random oracle model (CAROM) as in [BDF+11] and [AK22], in which adversaries are only allowed to classically query the random oracle. The restriction is well motivated for NISQ quantum adversaries and may remain plausible in the presence of early fault-tolerant quantum computers. Then, we show that an efficient simulation-secure one-time memory (OTM) is possible under CAROM. Our protocol uses only BB84 states and has quadratic communication: for a $λ$-bit message and integer-valued parameters $n=n(λ)$ and $\ell=\ell(λ)$, the construction uses $n\ell$ qubits and $(n+2)λ$ classical bits, and for any quantum adversary with at most $2^{\ell/2-1}-1$ classical queries to the random oracle, its simulation advantage is at most $(n+3)\left(\frac{3}{4}\right)^n.$ Hence exponentially small simulation advantage in $n$.
AI Summary
One-time memory (OTM) lets a receiver recover either of two encoded messages while learning nothing beyond one choice. The paper asks whether simulation-secure OTM can be constructed without restricting quantum circuit depth or storage. It works in the classically accessible random-oracle model (CAROM): adversaries may perform arbitrary quantum computation but can query the oracle only on classical inputs. The construction uses independently sampled BB84 words, oracle-generated tags that identify correctly measured words, and message masks formed from oracle outputs indexed by the words and the full basis pattern. For two $\lambda$-bit messages, $n$ words of length $\ell$ require $n\ell$ qubits and $(n+2)\lambda$ classical bits. Correctness error is at most $n2^{-\lambda}$. Against an adversary making at most $q$ classical oracle queries, the simulation advantage is bounded by $2^{1-n}+(n+1)(\tfrac12+\tfrac{q+1}{2^{\ell/2+1}})^n$. If $q\leq 2^{\ell/2-1}-1$, this becomes at most $(n+3)(3/4)^n$. The proof reduces single-word recovery with oracle queries to oracle-free list recovery, bounds the latter using overlap between computational and Hadamard bases, and applies perfect parallel repetition to obtain a multiword bound. A simulator programs mask responses when the first message branch is completed; failure requires completion of both branches. Security depends on classical-only oracle access, not merely a conventional computational assumption. Instantiation with a public hash function is discussed heuristically rather than proved. The construction removes depth and storage restrictions but retains this oracle-access restriction.
We used OpenAI Codex to assist with drafting and editing portions of the introduction and technical overview, as well as with formatting checks.
Error found: Token.Gen supplies the single basis bit θ_i to a mask oracle requiring the full basis pattern θ; using θ instead makes generation consistent with evaluation and the security proof. The proof of the true Projector sum bound contains an invalid equality and a reversed inequality, so that preliminary proof needs replacement.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.