Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.40194

Query-Limited RAM Programs and their Applications

Jiahui Liu, Justin Raizes, Bhaskar Roberts, Omri Shmueli

quant-phcs.CRSubmitted Sep 30, 2026• Announced Oct 1, 2026• 0 citations
arXivHTMLPDF

Abstract

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 $\textit{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 $\textit{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 $\textit{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.

AI Summary

The paper asks whether quantum one-time programs can support stateful computation with controlled access, rather than a single circuit evaluation, while making initial token size depend on code length rather than runtime. It introduces one-shot programs (OSPs), whose tokens can be generated publicly but permit only one effective input choice per serial number, and query-limited RAM programs (QLPs), which maintain hidden computational state across evaluations. Security is simulation-based: a limited-effective-query (LEQ) oracle maintains a coherent, stack-structured execution history, accommodating uncomputation rather than prohibiting every physical repeat query. The stated constructions derive OSPs from strongly unforgeable one-shot signatures, one-time programs from strongly unforgeable signature tokens, and QLPs from OSPs. Proofs use compressed random oracles, reversible caches, and signatures authenticating successive encrypted states and token serial numbers. Applications include code/Turing-machine tokens, $k$-time and budget-limited programs, terminal proofs of accumulated usage cost, and capability transfer through classical communication. For $k$-time programs, initial token size and generation time depend only polylogarithmically on $k$. The constructions operate in a classical-oracle model allowing superposition queries; replacing these oracles using indistinguishability obfuscation is heuristic. Plain-model definitions and constructions remain open. LEQ security does not automatically imply operational nonforking guarantees for arbitrary functionalities; these require separate analysis. The supplied text also contains unresolved proof-audit annotations identifying a mismatch in an acceptance-bit transition in the LEQ simulation proof.

Little sign of AI-generated textAI use disclosedStrong assumptionsUnclear writingPossible error
LLM tools have been used to check correctness of the proofs and provide feedback on our writing.

Central claim may not hold: The abstract omits that the constructions are proved only in the classical-oracle model, with plain-model constructions left open. The abstract's unrestricted anti-forking and anti-rollback language exceeds LEQ security, whose operational consequences require additional conditions on the functionality. The central simulation proof claims perfect equivalence between hybrids that give different acceptance bits on reachable states, leaving the main security theorem unestablished as written. The final squared-overlap inequality in Lemma lem:decomp-approx-identity is false, although the lemma's preceding trace-distance and norm bounds survive.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

On Best-Possible One-Time Programs

Aparna Gupte, Jiahui Liu, Luowen Qian +3 more

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.

cs.CRCross-listedarXiv:2603.00544•Mar 3, 2026•0 citations

Towards Quantum One-Time Memories from Stateless Hardware

Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless ( i.e. , reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114 n adaptive queries to the token (for n the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.

arXiv:1810.05226•Quantum•Apr 8, 2021•9 citations

Unclonable Cryptography in Linear Quantum Memory

Omri Shmueli, Mark Zhandry

Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys. Typically, this is to ensure the keys cannot be copied by an adversary, owing to the quantum no-cloning theorem. Unfortunately, due to quantum state's tendency to decohere, persistent quantum memory will likely be one of the most challenging resources for quantum computers. As such, it will be important to minimize persistent memory in quantum protocols. In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens. These are important unclonable primitives, where quantum signing keys allow for signing a single message but not two. Naturally, these quantum signing keys would require storage in long-term quantum memory. Very recently, the first OSS was constructed in a classical oracle model and also in the standard model, but we observe that the quantum memory required for these protocols is quite large. In this work, we significantly decrease the quantum secret key size, in some cases achieving asymptotically optimal size. To do so, we develop novel techniques for proving the security of cryptosystems using coset states, which are one of the main tools used in unclonable cryptography.

quant-pharXiv:2511.04633•Nov 7, 2025•1 citation

Quantum One-Time Programs, Revisited

Aparna Gupte, Jiahui Liu, Justin Raizes +2 more

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.

arXiv:2411.01876•ACM Symposium on Theory of Computing (STOC)•Jun 15, 2025•10 citations

Quantum One-Time Memories from Stateless Hardware

Anne Broadbent, Sevag Gharibian, Hong-Sheng Zhou

A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we show how to use quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where stateless hardware tokens alone cannot yield OTMs. In addition, our scheme is technologically simple. We prove security in the quantum universal composability framework, employing semi-definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].

arXiv:1511.01363•Leibniz international proceedings in informatics•Nov 4, 2015•5 citations

Towards Simple and Useful One-Time Programs in the Quantum Random Oracle Model

Lev Stambler

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 $\frac{1}{2m} + O(ε^\frac{1}{4})$. (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.

quant-pharXiv:2601.13258•Jan 20, 2026•0 citations
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\textit{query-limited RAM programs}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\textit{code length}code length (and not runtime), transferable kkk-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\textit{one-shot programs}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.
The paper asks whether quantum one-time programs can support stateful computation with controlled access, rather than a single circuit evaluation, while making initial token size depend on code length rather than runtime.
It introduces one-shot programs (OSPs), whose tokens can be generated publicly but permit only one effective input choice per serial number, and query-limited RAM programs (QLPs), which maintain hidden computational state across evaluations. Security is simulation-based: a limited-effective-query (LEQ) oracle maintains a coherent, stack-structured execution history, accommodating uncomputation rather than prohibiting every physical repeat query.
The stated constructions derive OSPs from strongly unforgeable one-shot signatures, one-time programs from strongly unforgeable signature tokens, and QLPs from OSPs. Proofs use compressed random oracles, reversible caches, and signatures authenticating successive encrypted states and token serial numbers. Applications include code/Turing-machine tokens, kkk-time and budget-limited programs, terminal proofs of accumulated usage cost, and capability transfer through classical communication. For kkk-time programs, initial token size and generation time depend only polylogarithmically on kkk.
The constructions operate in a classical-oracle model allowing superposition queries; replacing these oracles using indistinguishability obfuscation is heuristic. Plain-model definitions and constructions remain open. LEQ security does not automatically imply operational nonforking guarantees for arbitrary functionalities; these require separate analysis. The supplied text also contains unresolved proof-audit annotations identifying a mismatch in an acceptance-bit transition in the LEQ simulation proof.
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\mathsf{SZK} \not\subseteq \mathsf{BQP}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.
A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we propose a scheme for using quantum information, together with the assumption of stateless ( i.e. , reusable) hardware tokens, to build statistically secure OTMs. Via the semidefinite programming-based quantum games framework of Gutoski and Watrous [STOC 2007], we prove security for a malicious receiver making at most 0.114 n adaptive queries to the token (for n the key size), in the quantum universal composability framework, but leave open the question of security against a polynomial amount of queries. Compared to alternative schemes derived from the literature on quantum money, our scheme is technologically simple since it is of the "prepare-and-measure" type. We also give two impossibility results showing certain assumptions in our scheme cannot be relaxed.
Quantum cryptography is a rapidly-developing area which leverages quantum information to accomplish classically-impossible tasks. In many of these protocols, quantum states are used as long-term cryptographic keys. Typically, this is to ensure the keys cannot be copied by an adversary, owing to the quantum no-cloning theorem. Unfortunately, due to quantum state's tendency to decohere, persistent quantum memory will likely be one of the most challenging resources for quantum computers. As such, it will be important to minimize persistent memory in quantum protocols. In this work, we consider the case of one-shot signatures (OSS), and more general quantum signing tokens. These are important unclonable primitives, where quantum signing keys allow for signing a single message but not two. Naturally, these quantum signing keys would require storage in long-term quantum memory. Very recently, the first OSS was constructed in a classical oracle model and also in the standard model, but we observe that the quantum memory required for these protocols is quite large. In this work, we significantly decrease the quantum secret key size, in some cases achieving asymptotically optimal size. To do so, we develop novel techniques for proving the security of cryptosystems using coset states, which are one of the main tools used in unclonable cryptography.
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.
A central tenet of theoretical cryptography is the study of the minimal assumptions required to implement a given cryptographic primitive. One such primitive is the one-time memory (OTM), introduced by Goldwasser, Kalai, and Rothblum [CRYPTO 2008], which is a classical functionality modeled after a non-interactive 1-out-of-2 oblivious transfer, and which is complete for one-time classical and quantum programs. It is known that secure OTMs do not exist in the standard model in both the classical and quantum settings. Here, we show how to use quantum information, together with the assumption of stateless (i.e., reusable) hardware tokens, to build statistically secure OTMs. This is in sharp contrast with the classical case, where stateless hardware tokens alone cannot yield OTMs. In addition, our scheme is technologically simple. We prove security in the quantum universal composability framework, employing semi-definite programming results of Molina, Vidick and Watrous [TQC 2013] and combinatorial techniques of Pastawski et al. [Proc. Natl. Acad. Sci. 2012].
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−ε)(1 - ε)(1−ε) success on one basis has conjugate-basis guessing probability at most 12m+O(ε14)\frac{1}{2m} + O(ε^\frac{1}{4})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.