Query-Limited RAM Programs and their Applications

AI summary

Overview

Research area: Quantum cryptography, specifically quantum one-time programs, unclonable quantum tokens, one-shot signatures, and delegation of computation.

Technical level: Advanced. The paper is a theoretical cryptography paper that relies on simulation-based security, compressed-oracle techniques, one-shot signatures, and RAM-style computation. It contains no experiments, datasets, or empirical benchmarks.

Scope: The paper introduces one-shot programs (OSPs) and query-limited RAM programs (QLPs), constructs them in a classical oracle model from one-shot signatures, and develops applications including (k)-time programs, pay-per-use programs, and semi-quantum transfer.

What This Paper Is About

Quantum one-time programs (OTPs) encode a functionality into a quantum token that can be evaluated once and then becomes unusable, but they are stateless and require a new token for every evaluation. This paper asks whether the one-time paradigm can be extended to stateful, query-limited access to RAM programs and Turing Machines, with token size depending on the code length rather than the runtime, and without an always-online provider enforcing every query. The authors introduce query-limited RAM programs (QLPs), build them from a new primitive called one-shot programs (OSPs), and show applications such as (k)-time programs, budget-limited and pay-per-use programs, and low-communication Software-as-a-Service access.

Key Contributions

1. One-shot programs (OSPs). The paper defines OSPs, which upgrade quantum one-time programs with the generator-resistant unclonability of one-shot signatures. It constructs an OSP compiler from any one-shot signature scheme in a classical oracle model (Theorem 4.3). The same modular construction shows that any quantum signature token scheme yields a one-time program compiler (Theorem 4.1), removing reliance on the algebraic structure of coset states used in prior OTP constructions. The authors also show that OSPs imply one-shot signatures in a classical oracle model (Section B.3).

2. Query-limited RAM programs (QLPs). The paper defines QLPs, a RAM generalization of OTPs that supports controlled sequences of evaluations over a stateful program while preventing adversarial forking or rollback of computational state. It introduces the limited-effective query (LEQ) oracle, a RAM generalization of the single-effective query (SEQ) oracle, and constructs a QLP compiler from an OSP compiler with a formal security proof in a classical oracle model (Theorem 5.1).

3. Applications of QLPs. The paper derives one-time programs for code/RAM programs and more generally (k)-time programs, where both token size and, in the construction, token generation time depend only polylogarithmically on (k). It also introduces pay-per-use (PPU) programs, where a user can later prove a bound on accumulated cost, and semi-quantum QLPs with a classical-message Transfer protocol (Theorem 1.1).

4. Clarifying the relationship between signing tokens and one-time computation. The paper gives generic constructions connecting signature-token primitives and quantum one-time programs, essentially showing that one-time signing programs imply one-time general computation.

Main Findings

• Public token generation is compatible with one-time security when tokens carry serial numbers. In an OSP, anyone can generate a token ((|T\rangle, s)) using the public common reference string. The serial number (s) is an input to the compiled functionality (f(s,x;r)), so a new token enables evaluation at its associated serial number. Security requires at most one effective choice of (x) per serial number, rather than one effective evaluation overall.

• The LEQ oracle generalizes SEQ to many serial numbers. The LEQ oracle maintains a compressed database of records ((s,x,r)) with at most one record per serial number. On a query ((s,x)), it refuses to answer in branches containing a different input (x') for the same serial number; otherwise it coherently evaluates (f(s,x;H(s,x))) and uncomputes its workspace.

• The QLP construction prevents state forking and rollback. A QLP compiler consists of a program compiler (\widetilde{P_0} \leftarrow \mathsf{PGen}(P)) and an evaluation algorithm ((y,\widetilde{P_{\mathsf{st}'}}) \leftarrow \mathsf{Eval}(x,\widetilde{P_{\mathsf{st}}})). The evaluator may choose the classical input (x), but the security guarantee prevents illegal changes to the program’s inner state.

• Token size for Turing Machines depends on code length, not runtime. The abstract states that QLPs enable quantum tokens for Turing Machines whose size depends only on code length and not on runtime. For (k)-time programs, the paper states that token size and, in their construction, generation time depend only polylogarithmically on (k).

• Semi-quantum transfer uses only classical messages. In the semi-quantum QLP construction, the receiver generates a fresh next-token serial number (s'), the sender consumes its current token to execute a special transfer step that authenticates (s'), and the receiver obtains the updated classical state plus a fresh token enabling the next evaluation. Correctness holds for arbitrary polynomial-length interleavings of Eval and Transfer operations.

• The constructions are in the classical oracle model. Security is simulation-based with respect to a classical oracle. The paper states that the oracles can be heuristically instantiated efficiently using indistinguishability obfuscation and one-way functions. Plain-model constructions are left open.

• Comparison with prior work. Table 1 compares this work with [GLR+25], [GM24], and [Sta25a]. The paper states that [Sta25a] also proposes RAM oracles and semi-quantum OTPs but uses classical measured oracles and single-physical-query security, while this work’s OSS-based OSP and QLP add a decentralized feature: anyone can generate their own tokens and transfer programs to others via classical communication.

Methodology in Plain English

The authors follow the simulation paradigm used for OTPs: instead of counting how many times an adversary calls an interface, they ask how much “effective” input/output information the adversary extracts. Their ideal-world oracle, the LEQ oracle, records effective queries in a compressed quantum database and refuses to answer once an adversary has effectively learned two distinct inputs for the same serial number. A secure construction must be indistinguishable from this oracle.

To build one-shot programs, they use a “sign, then evaluate” approach. The compiled program is a classical oracle that evaluates (f(s,x;G(s,x,\sigma))) only when the query contains a valid one-shot signature (\sigma) on the message (x) under serial number (s). An honest evaluator uses its quantum token to sign (x) and then queries the oracle.

The security proof has three main steps. First, the authors add an SEQ-style check that refuses a valid query if the database already records a different ((x',\sigma')) for the same serial, arguing that any noticeable change would yield two valid message-signature pairs and contradict strong unforgeability of the one-shot signature. Second, they reversibly separate the signature information from each record using a quantum cache and a Split operation, so that the database can record only ((s,x,r)) while the signature information remains available in the cache. Third, they remove the signature from the ideal oracle’s database without losing the correlations needed to uncompute. This extends the coherent-caching approach of [GLR+25] from a single record to many records indexed by serial numbers, and uses Zhandry’s compressed-oracle technique.

QLPs are then constructed from OSPs by treating the stateful program’s sequence of evaluations as a controlled sequence of token-authorized steps. The applications follow from this construction, including a transfer protocol in which the sender consumes a token to authorize a fresh serial number chosen by the receiver.

Why This Matters

Impact on research. The paper extends quantum one-time computation from a single stateless evaluation to stateful, query-limited RAM computation. It connects two previously separate lines of work, one-shot signatures and quantum one-time programs, and shows that the stronger unclonability of one-shot signatures can strengthen the functionality of one-time programs. It also introduces a new security model, the LEQ oracle, for reasoning about bounded access to stateful computation.

Real-world applications discussed in the paper:

• Software-as-a-Service and restricted access to AI models. The paper uses restricted query access to a powerful AI model as a motivating example. QLPs allow a user to evaluate locally while the access policy is enforced by the program itself, rather than by an always-online provider executing every query.

• Tokens for code and Turing Machines. QLPs yield one-time programs for code/RAM programs and quantum tokens for Turing Machines whose size depends only on code length, not runtime.

• (k)-time and budget-limited programs. The paper describes transferable (k)-time or budget-limited programs, where a program may be executed for up to (k) steps and token size and generation time depend only polylogarithmically on (k).

• Pay-per-use programs. A user can repeatedly evaluate a program and later prove to a verifier an upper bound on the total cost incurred, with the internal state kept hidden.

• Low-communication delegation and semi-quantum issuance. The paper states that these applications offer new mechanisms for delegating computation with minimal communication, and that a semi-quantum QLP can have a purely classical issuer transferring the restricted capability over a classical channel.

Industry relevance. The results are theoretical and depend on classical oracle models, one-shot signatures, and heuristic instantiation using indistinguishability obfuscation and one-way functions. They are relevant to cloud AI providers, software licensing, delegated computation, and access control for quantum-era systems, but the paper does not report an implementation, performance benchmark, or deployment.

Future Directions

1. Plain-model security for stateful query-limited access. The paper lists formulating a security definition for query-limited access to stateful/RAM programs with constructions in the plain model, without oracles, without running into impossibilities. It notes that because OTPs are a special case of QLPs, the plain-model impossibilities for SEQ simulation security discussed in [GLR+25] apply to QLPs as well.

2. Constructions from indistinguishability obfuscation and weaker assumptions. Building on the first direction, the paper calls for constructions in the plain model from indistinguishability obfuscation and, more desirably, weaker standard assumptions, for generic or specialized functionalities.

3. Generic semi-quantum transformations. The paper states that its construction does not transform any QLP generically into a semi-quantum version. It instead focuses on an intermediate structure generically implied by one-shot programs. A general transformation remains open.

4. Broader applications and instantiations. The paper presents preliminary applications and leaves open further uses of QLPs, as well as efficient instantiations of the oracle-based constructions.

Target Audience

This paper is most useful to quantum cryptography researchers, theoretical cryptographers working on one-time programs, one-shot signatures, obfuscation, and delegation of computation, and graduate students with a background in simulation-based security and quantum oracle techniques. It is also relevant to industry research teams exploring cryptographic access control for cloud services and AI models, though the advanced technical level and oracle-model constructions make it primarily a theory contribution rather than an engineering blueprint.

Authors’ 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.