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
ℓ=ℓ(λ), the construction uses
nℓ qubits and
(n+2)λ classical bits, and for any quantum adversary with at most
2ℓ/2−1−1 classical queries to the random oracle, its simulation advantage is at most
(n+3)(43)n. Hence exponentially small simulation advantage in
n.