Quantum one-time memory possible with restricted classical queries
Beyond NISQ Assumptions: One-time Memory in the Classically Accessible Random-Oracle Model
Cryptography and Security
Summary
Certain cryptographic functions are impossible using only classical computers but become achievable with quantum technology. Previous designs assumed quantum attackers had limited power, called NISQ devices, but stronger quantum machines are coming. The authors show you can create a secure one-time memory device assuming attackers can only make classical queries to a random function. Their method uses simple quantum states and prevents attackers from gaining meaningful advantage, even with some quantum computing power.
What this means in practice
- •For quantum cryptography engineers: Build one-time memory devices that remain secure under realistic quantum attack assumptions with limited quantum queries to the random oracle.
- •For quantum communication teams: Implement protocols using BB84 quantum states for efficient one-time secure storage with guaranteed security against quantum attackers with bounded oracle access.
Authors
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$.