Paper 2026/413

On Best-Possible One-Time Programs

Abstract

One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware assumptions. Quantum measurement offers a possible physical basis for one-time use: obtaining an output may irreversibly disturb the program needed for further computation. Yet deterministic functionalities remain impossible due to gentle-measurement attacks (Broadbent, Gutoski and Stebila, 2013). While recent works achieve positive results for randomized functionalities with high-entropy outputs (Gunn, Movassagh 2025; Gupte, Liu, Raizes, Roberts, Vaikuntanathan 2025), the fundamental limits and the strongest achievable security notions remain poorly understood. Inspired by classical obfuscation, we ask for a “best-possible” one-time compiler: a generic transformation that, for any functionality, leaks the least amount of information compared with any other one-time implementation. We show that a generic best-possible one-time compiler cannot exist even for classical randomized functionalities assuming $\mathsf{SZK} \not\subseteq \mathsf{BQP}$. Given this impossibility, we identify a natural subclass of one-time compilers called “testable one-time program” compilers, which output quantum states augmented with reflection programs for themselves. (1) We formulate a simplified, generalized Single-Effective-Query (SEQ) simulation security notion for quantum channels. The definition uses self-adjoint implementations whose behavior under arbitrary quantum interactions depends only on the channel. We show that SEQ security implies best-possible testable one-time security. (2) We construct SEQ-secure OTPs for all quantum functionalities in the classical oracle model, yielding the first positive results for arbitrary quantum channels beyond classical randomized functionalities. Thus, SEQ security could serve as a testable one-time analogue of virtual black-box (VBB) security in the many-time obfuscation setting. Finally, we propose stateful quantum indistinguishability obfuscation (stateful quantum iO) — quantum state obfuscation for stateful quantum programs. It implies best-possible testable OTPs and is achievable in the classical oracle model, thus giving us a promising approach towards best-possible testable OTPs in the plain model.

Note: 72 pages; preprint. Substantially revised exposition and proofs; strengthened impossibility results and added a separation between SEQ and testable security.