Paper 2025/2319

One-Time Memories Secure against Depth-Bounded Quantum Circuits

Abstract

A one-time memory (OTM) is a useful cryptographic primitive, classically modeled after a non-interactive oblivious transfer. It is well known that secure OTMs (and more generally one-time deterministic programs) cannot exist in the standard model in either the classical or quantum setting due to Broadbent et al. (CRYPTO'13). Broadbent et al.\ circumvented this impossibility by assuming the existence of hardware tokens that cannot be queried in superposition. In this work, we take a different approach. Building on Liu's assumption (ITCS'23) that adversaries are limited to depth-bounded quantum circuits, we present two OTM constructions. The first is efficiently realizable and secure against adversaries restricted to constant-depth quantum circuits. The second is a feasibility result that achieves security against adversaries limited to $\mathcal{O}(\lambda^\gamma)$-depth quantum circuits by ensuring that a successful attack would necessarily require deeper quantum computations, where $\lambda^\gamma$ is a polynomial in the security parameter $\lambda$. Our results therefore extend prior work, which either relied on hardware assumptions or considered only constant-depth-bounded adversaries. As a result, by combining our proposed quantum OTMs with the framework of Broadbent et al. (CRYPTO'13), one can also realize quantum one-time programs (OTPs) for deterministic programs.

Note: Indocrypt 2025