One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware. Quantum measurement suggests a physical basis for one-time use, yet deterministic functionalities remain impossible due to gentle-measurement attacks (Broadbent, Gutoski and Stebila, 2013). Recent constructions cover randomized functionalities with high-entropy outputs (Gunn, Movassagh 2025; Gupte et al., 2025), but the strongest achievable security remains unclear.
Inspired by classical obfuscation, we ask for a "best-possible" one-time compiler that, for any functionality, leaks the least information compared with any other one-time implementation. We prove that such a generic compiler cannot exist even for classical randomized functionalities assuming $\mathsf{SZK} \not\subseteq \mathsf{BQP}$.
We then identify a natural subclass: testable OTP compilers, which output quantum states augmented with reflection programs for themselves. We formulate a simplified, generalized Single-Effective-Query (SEQ) simulation security notion for quantum channels, using self-adjoint implementations whose behavior under arbitrary quantum interactions depends only on the channel. SEQ security implies best-possible testable one-time security. We construct SEQ-secure OTPs for all quantum functionalities in the classical oracle model, giving the first positive results for arbitrary quantum channels beyond classical randomized functionalities. SEQ security could thus serve as a testable one-time analogue of virtual black-box (VBB) security.
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, offering an approach towards best-possible testable OTPs in the plain model.
Comments
72 pages; preprint. Substantially revised exposition and proofs; strengthened impossibility results and added a separation between SEQ and testable security
One-time programs (OTPs) aim to let a user evaluate a program on a single input while revealing nothing else. Classical OTPs require hardware. Quantum measurement suggests a physical basis for one-time use, yet deterministic functionalities remain impossible due to gentle-measurement attacks (Broadbent, Gutoski and Stebila, 2013). Recent constructions cover randomized functionalities with high-entropy outputs (Gunn, Movassagh 2025; Gupte et al., 2025), but the strongest achievable security remains unclear.
Inspired by classical obfuscation, we ask for a "best-possible" one-time compiler that, for any functionality, leaks the least information compared with any other one-time implementation. We prove that such a generic compiler cannot exist even for classical randomized functionalities assuming SZK⊆BQP.
We then identify a natural subclass: testable OTP compilers, which output quantum states augmented with reflection programs for themselves. We formulate a simplified, generalized Single-Effective-Query (SEQ) simulation security notion for quantum channels, using self-adjoint implementations whose behavior under arbitrary quantum interactions depends only on the channel. SEQ security implies best-possible testable one-time security. We construct SEQ-secure OTPs for all quantum functionalities in the classical oracle model, giving the first positive results for arbitrary quantum channels beyond classical randomized functionalities. SEQ security could thus serve as a testable one-time analogue of virtual black-box (VBB) security.
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, offering an approach towards best-possible testable OTPs in the plain model.
We construct simulation-secure one-time memories (OTM) in the random oracle model, and present a plausible argument for their security against quantum adversaries with bounded and adaptive depth. Our contributions include: (1) A simple scheme where we use only single-qubit Wiesner states and conjunction obfuscation (constructible from LPN): no complex entanglement or quantum cryptography is required. (2) A new POVM bound where e prove that any measurement achieving (1−ε) success on one basis has conjugate-basis guessing probability at most 2m1+O(ε41). (3) Simultation-secure OTMs in the quantum random oracle model where an adversary can only query the random oracle classically. (4) Adaptive depth security where, via an informal application of a lifting theorem from Arora et al., we conjecture security against adversaries with polynomial quantum circuit depth between random oracle queries.
Security against adaptive, depth-bounded, quantum adversaries captures many realistic attacks on OTMs built from single-qubit states; our work thus paves the way for practical and truly secure one-time programs. Moreover, depth bounded adaptive adversarial models may allow for encoding one-time memories into error corrected memory states, opening the door to implementations of one-time programs which persist for long periods of time.
One-time programs (Goldwasser, Kalai and Rothblum, CRYPTO 2008) are functions that can be run on any single input of a user's choice, but not on a second input. Classically, they are unachievable without trusted hardware, but the destructive nature of quantum measurements seems to provide a quantum path to constructing them. Unfortunately, Broadbent, Gutoski and Stebila showed that even with quantum techniques, a strong notion of one-time programs, similar to ideal obfuscation, cannot be achieved for any non-trivial quantum function. On the positive side, Ben-David and Sattath (Quantum, 2023) showed how to construct a one-time program for a certain (probabilistic) digital signature scheme, under a weaker notion of one-time program security. There is a vast gap between achievable and provably impossible notions of one-time program security, and it is unclear what functionalities are one-time programmable under the achievable notions of security. In this work, we present new, meaningful, yet achievable definitions of one-time program security for probabilistic classical functions. We show how to construct one time programs satisfying these definitions for all functions in the classical oracle model and for constrained pseudorandom functions in the plain model. Finally, we examine the limits of these notions: we show a class of functions which cannot be one-time programmed in the plain model, as well as a class of functions which appears to be highly random given a single query, but whose one-time program form leaks the entire function even in the oracle model.
Quantum one-time programs (Broadbent, Gutoski and Stebila, CRYPTO 2013) or OTPs for short, enable a functionality to be encoded into a quantum token that can be evaluated on a single chosen input and then becomes unusable. While powerful, this primitive is inherently stateless and tied to a setting in which a quantum token needs to be issued and distributed for every single evaluation of a circuit. This raises a natural question: can the one-time computation paradigm be extended to richer, stateful forms of controlled access, and would such an extension offer inherent advantages beyond standard OTPs?
We introduce query-limited RAM programs (QLPs), a RAM-generalization of QOTPs that supports structured, stateful computation under bounded or policy-driven access. QLPs allow controlled sequences of evaluations while preventing adversarial forking or rollback of computational state. This enables new applications beyond stateless one-time programs, including quantum tokens for Turing Machines whose size depends only on code length (and not runtime), transferable k-time or budget-limited programs, and low-communication mechanisms for delegating computation in settings such as Software-as-a-Service.
To construct QLPs, we introduce one-shot programs, unifying one-shot signatures (Amos, Georgiou, Kiayias and Zhandry, STOC 2020) with the single effective query paradigm (Gupte, Liu, Raizes, Roberts and Vaikuntanathan, STOC 2025). We prove that one-shot programs generically imply query-limited programs, demonstrating that the strengthened unclonability guarantees of one-shot signatures translate into enhanced functionality. Along the way, we clarify the relationship between signature-token primitives and quantum one-time programs via generic constructions, essentially showing that one-time signing programs imply one-time general computation.
A major unresolved question in quantum cryptography is whether it is possible to obfuscate arbitrary quantum computation. Indeed, there is much yet to understand about the feasibility of quantum obfuscation even in the classical oracle model, where one is given for free the ability to obfuscate any classical circuit. In this work, we develop a new array of techniques that we use to construct a quantum state obfuscator, a powerful notion formalized recently by Coladangelo and Gunn (arXiv:2311.07794) in their pursuit of better software copy-protection schemes. Quantum state obfuscation refers to the task of compiling a quantum program, consisting of a quantum circuit C with a classical description and an auxiliary quantum state ψ, into a functionally-equivalent obfuscated quantum program that hides as much as possible about C and ψ. We prove the security of our obfuscator when applied to any pseudo-deterministic quantum program, i.e. one that computes a (nearly) deterministic classical input / classical output functionality. Our security proof is with respect to an efficient classical oracle, which may be heuristically instantiated using quantum-secure indistinguishability obfuscation for classical circuits. Our result improves upon the recent work of Bartusek, Kitagawa, Nishimaki and Yamakawa (STOC 2023) who also showed how to obfuscate pseudo-deterministic quantum circuits in the classical oracle model, but only ones with a completely classical description. Furthermore, our result answers a question of Coladangelo and Gunn, who provide a construction of quantum state indistinguishability obfuscation with respect to a quantum oracle, but leave the existence of a concrete real-world candidate as an open problem. Indeed, our quantum state obfuscator together with Coladangelo-Gunn gives the first candidate realization of a “best-possible” copy-protection scheme for all polynomial-time functionalities. Our techniques deviate significantly from previous works on quantum obfuscation. We develop several novel technical tools which we expect to be broadly useful in quantum cryptography. These tools include a publicly-verifiable, linearly-homomorphic quantum authentication scheme with classically-decodable ZX measurements (which we build from coset states), and a method for compiling any quantum circuit into a ”linear + measurement” () quantum program: an alternating sequence of CNOT operations and partial ZX measurements.
Program obfuscation aims to conceal a computer program's internal structure while preserving its functionality. A central open problem is whether an obfuscation scheme for arbitrary quantum circuits exists. Despite several efforts toward this goal, prior works have succeeded only in obfuscating quantum circuits that implement either pseudo-deterministic functions or unitary transformations. Although unitary transformations already include a broad class of quantum computations, many important quantum tasks, such as state preparation, quantum sampling, and quantum error correction, go beyond unitaries and are described by general completely positive trace-preserving (CPTP) maps.
In this work, we construct the first quantum ideal obfuscation scheme for arbitrary quantum circuits that support quantum inputs and outputs in the classical oracle model assuming post-quantum one-way functions, thereby resolving an open problem raised in Bartusek et al. (STOC 2023), Bartusek, Brakerski, and Vaikuntanathan (STOC 2024), and Huang and Tang (FOCS 2025). At the core of our construction lies a novel primitive that we introduce, called the subspace-preserving strong pseudorandom unitary (spsPRU). An spsPRU is a family of efficient unitaries that fix every vector in a given linear subspace S, while acting as a Haar random unitary on its orthogonal complement S⊥ under both forward and inverse oracle queries. Furthermore, by instantiating the classical oracle model with the ideal obfuscation scheme for classical circuits proposed by Jain et al. (CRYPTO 2023) and later enhanced by Bartusek et al. (CRYPTO 2026), our obfuscation scheme can also be realized in the quantumly accessible pseudorandom oracle model.
We study minimum-error identification of an unknown single-bit Boolean function given black-box (oracle) access with one allowed query. Rather than stopping at an abstract optimal measurement, we give a fully constructive solution: an explicit state preparation and an explicit measurement unitary whose computational-basis readout achieves the Helstrom-optimal success probability 3/4 for distinguishing the four possible functions. The resulting circuit is low depth, uses a fixed gate set, and (in this smallest setting) requires no entanglement in the input state. Beyond the specific example, the main message is operational. It highlights a regime in which optimal oracle discrimination is not only well-defined but implementably explicit: the optimal POVM collapses to a compact gate-level primitive that can be compiled, verified, and composed inside larger routines. Motivated by this, we discuss a "what if" question that is open in spirit: for fixed (n,m,k), could optimal k-query identification (possibly for large hypothesis classes) admit deterministic, closed-form descriptions of the inter-query unitaries and the final measurement unitary acting on the natural n+m-qubit input--output registers (and, if needed, small work registers)? Even when such descriptions are not compact and do not evade known circuit-complexity barriers for generic Boolean functions, making the optimum constructive at the circuit level would be valuable for theory-to-hardware translation and for clarifying which forms of "oracle access" are physically meaningful.