PaperlayerView exact revision on arXiv

Source-linked AI summary

Query-Limited RAM Programs and their Applications

Jiahui Liu, Justin Raizes, Bhaskar Roberts, Omri Shmueli

arXiv:2609.40194v1quant-phcs.CR

TL;DR

Quantum one-time programs leave open how to control access to computation whose state changes across evaluations. The paper constructs query-limited RAM programs from one-shot programs, and reports a compiler for randomized RAM programs alongside applications including stateful transfer. Its stated limitation includes a compressed-oracle implementation issue for deterministic queries.

  • Problem

    Quantum one-time programs address single stateless evaluations, leaving open controlled access to stateful programs whose future behavior depends on prior use.

    Source: §1 · p. 3

  • Method

    The paper introduces one-shot programs and constructs query-limited RAM program compilers from them, using a limited-effective-query oracle to track effective execution paths.

    Source: §1.1 · p. 6, §2.3 · p. 14

  • Results

    The construction is a QLP compiler for any family of randomized RAM programs, and semi-quantum QLPs support classical-message transfer.

    Source: §1.1 · p. 6, §5.2 · p. 56

  • Takeaways & Limitations

    A transferred program inherits the sender's RAM state and remaining query allowance, so a k-time program used k' times transfers as a (k−k')-time program.

    Source: Semi-Quantum Query-Limited Programs · p. 18

    A naive compressed-oracle implementation can get stuck after deterministic queries, while appending randomness makes the ideal functionality depend on the security parameter.

    Source: §2.3 · p. 15

Abstract

from arXiv · show

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.

1 Introduction

Quantum one-time programs provide single-use access, but leave open how to control stateful computation without repeated token issuance or state forking. The paper introduces one-shot programs and query-limited RAM programs, then develops constructions and applications that extend controlled access beyond stateless evaluation.

1 Introduction

  • Stateful access remains open: OTPs support one-time stateless evaluation, while a stateful program's future behavior may depend on prior use.In SaaS, state can include both the query count and the conversation's inner memory; issuing an OTP for every query remains an option.Source: §1 · p. 3
  • The paper seeks locally evaluable quantum tokens sized by program code rather than possible future computation, with access policy enforced by the program.The motivating server-based approaches require work proportional to client computation and at least the number of queries, plus Ω(k) communication for k queries.Source: §1 · pp. 3–4

1.1 Results and Future Work

  • One-shot programs extend OTP unclonability to the generator-resistant guarantee of one-shot signatures, and can be constructed from one-shot signatures.The paper describes OTP and OSS guarantees as complementary: one-time obfuscated functionality versus generator-resistant unclonability.Source: §1.1 · pp. 4–5, §1 · p. 4
  • In the classical oracle model, one-shot signatures yield one-shot program compilers, while quantum signature tokens yield one-time program compilers.The OTP compiler does not rely on the coset-state algebraic structure used by prior constructions.Source: §1.1 · p. 5
  • The authors define QLPs for stateful programs and construct a QLP compiler from an OSP compiler, using a RAM-generalized limited-effective-query oracle.QLP evaluation returns an output and advances program state while preventing illegal changes to that state.Source: §1.1 · pp. 5–6
  • QLPs yield code/RAM and k-time programs whose token size and, in the construction, generation time depend polylogarithmically on k.A transferred program inherits the sender's RAM state and remaining query allowance; using k' queries from a k-time program leaves k−k' queries.Source: §1.1 · p. 6
  • Pay-per-use programs let users evaluate a stateful program and later prove a bound on its accumulated cost; k-time and pay-per-use programs offer resource-light SaaS delegation.The proof interface provides a classically verifiable proof that accumulated cost equals or is bounded by c.Source: §1.1 · p. 6
  • The paper also gives a semi-quantum QLP construction with classical-message transfer, while prior work [Sta25a] uses measured oracles and requires vendor communication for each incoming receiver.The stated semi-quantum result follows from QLP compilers based on OSP tokens.Source: §1.1 · p. 6, §1.2 · p. 8

2 Technical Overview

The technical overview sets out how query-limited RAM programs support stateful computation under ordered, policy-controlled access, defining and constructing them through one-shot programs and a limited-effective-query model. It also covers applications to pay-per-use access and classical transfer, and a construction of one-shot signatures from blind-unforgeable schemes.

2.1 Previous Work on Quantum One-Time Programs

  • The physical-query definition of is impossible because deterministic outputs can be measured without disrupting the token, while SEQ security instead limits effective information extracted from it.The SEQ oracle uses a compressed random-oracle database to track queries.Source: §2.1 · pp. 8–9

2.2 One-Shot Programs

  • OSP security allows public token generation but restricts each serial number to one effective choice of input, enabling serial-dependent functionality and stateful computation.A newly generated token enables evaluation at its associated serial; the restriction applies separately to each serial.Source: §2.2 · pp. 10–11
  • OSP compilers use one-shot signature tokens to sign the input, then evaluate the function through a verified classical oracle with randomness indexed by the serial, input, and signature.The construction inherits setup and token generation from a strongly unforgeable one-shot signature scheme.Source: §2.2 · p. 11
  • The OSP security proof uses strong unforgeability and a reversible cache to simulate coherent queries and uncomputation using only SEQ access.The cache preserves signature information as the database records are split, updated, or erased; strong unforgeability justifies restricting each serial to one valid pair and then making the check depend only on the input.Source: §2.2 · p. 12
  • The authors construct SEQ-secure one-time programs from any signature tokens, combining their use with the stronger security notion than the measurement-enforced notion of.The construction uses signature tokens instead of the subspace coset states in.Source: §2.2 · pp. 12–13

2.3 Query-Limited RAM Programs

  • QLPs support successive stateful evaluations, with program state enforcing k-time limits, accumulated budgets, or general working-memory behavior.Correctness covers polynomial-length input sequences; evaluators choose inputs but do not directly choose internal memory states.Source: §2.3 · p. 13
  • The LEQ oracle permits repeated evaluations as program state updates and coherent uncomputation, while restricting access to one effective execution path through an ordered database.The program memory states are not exposed to the simulator.Source: §2.3 · p. 14
  • QLPs expose computation as a stack: evaluators may repeat the latest query or advance to the next, but cannot access middle states, preserving a complete history.Security must also make a real QLP indistinguishable from an oracle that forbids middle queries, even though a real evaluator could re-evaluate them.Source: §2.3 · p. 15
  • A naive compressed-oracle database can get stuck when deterministic or gentle queries go unrecorded, so the design uses a fresh one-shot program run to record each query and continue computation.Without this change, a later query could be answered using an earlier memory state, leaving a simulator unable to learn the correct response.Source: §2.3 · p. 15
  • Each step consumes a one-shot token and replaces the sole valid signed state-serial pair, preventing forks unless an adversary reuses a serial on distinct inputs or forges a signature.The security proof establishes ordered, consistent database entries and uses a cache to translate between the SEQ and LEQ oracle interfaces.Source: §2.3 · pp. 16–17

2.4 Applications

  • QLPs capture k-time programs and programs with a prefixed budget, and the overview presents further applications.Source: §2.4 · p. 17

Pay-Per-Use Programs

  • Pay-per-use programs let users query first and pay afterward, with a proof that their effective queries—the queries whose information was obtained—cost the amount claimed.The challenger checks a valid proof against the LEQ oracle’s query database.Source: Pay-Per-Use Programs · p. 17

Semi-Quantum Query-Limited Programs

  • Semi-quantum QLPs let a sender transfer a program to another user using classical communication, transferring its RAM state and remaining query or budget allowance.For a k-time program after k′ queries, the receiver obtains a (k−k′)-time program.Source: Semi-Quantum Query-Limited Programs · pp. 17–18
  • A blind-unforgeable signature scheme combined with a one-shot program compiler yields one-shot signatures whose verification is essentially the underlying scheme’s verification.The one-shot program implements signing keyed by a serial number; one-shot security enforces per-serial use, while blind-unforgeability supplies post-quantum unforgeability.Source: Semi-Quantum Query-Limited Programs · p. 18

3 Preliminaries

This section establishes the oracle-indistinguishability and compressed-oracle tools and cryptographic definitions used in the paper, including signature-token, one-shot-signature, and one-time-program security notions. It also shows that post-quantum secure pseudorandom permutations suffice for qIND-qCPA-secure secret-key encryption.

3 Preliminaries

  • Oracle distributions are perfectly indistinguishable when unbounded quantum-query distinguishers have zero advantage, and computationally indistinguishable when QPT distinguishers have negligible advantage.Source: §3 · p. 18

3.1 Compressed Oracles

  • The compressed oracle purifies randomness into a superposition over functions and records queries in a database register holding a partial truth table.The database is initialized empty before queries are processed.Source: §3.1 · pp. 18–19

A Useful Eigenbasis:

  • The joint query/database basis is orthonormal, and for nonzero ỹ′ a compressed-oracle query permutes its basis vectors while modifying only the database register.These are the claims of Lemmas 3.1 and 3.2.Source: A Useful Eigenbasis · pp. 19, 21
  • Lemma 3.3 shows the compressed oracle acts almost like CO′ when an input-output pair is known externally, with the guarantee scaling to partial output knowledge.The lemma considers a random oracle whose output is split into finite, nonempty components.Source: A Useful Eigenbasis · p. 22

3.2 Pseudorandom Functions

  • A pseudorandom function is an efficient, length-preserving keyed function that no QPT distinguisher can distinguish from random with more than negligible advantage.The definition applies for every security parameter.Source: §3.2 · p. 24

3.3 Blind-Unforgeable Signatures

  • Blind unforgeability requires that a QPT adversary cannot produce an accepted signature for a message in its chosen blinding set, which the signing oracle answers with ⊥.The oracle signs messages outside the set.Source: §3.3 · p. 25

3.4 Signature Tokens

  • Generalized signature tokens extend one-message quantum signing with serial-number security, capturing one-shot schemes via sk=pk and regular schemes via one serial plus strong unforgeability.An adversary cannot produce two valid message-signature pairs for the same serial number.Source: §3.4 · pp. 25–26
  • A one-time signature token scheme uses a single valid serial number s*, rejects other serials, and prevents two different valid message-signature pairs.The scheme is specified as a strongly unforgeable special case of generalized signature tokens.Source: §3.4 · pp. 26–27
  • One-shot signatures are generalized signature tokens whose TokenGen procedure is public, so sk = pk.Source: §3.4 · p. 27

3.5 One-Time Programs

  • A one-time program compiler generates a quantum program from a function description, evaluates it on a classical input, and is correct when its output distribution is statistically close to the function’s.Source: §3.5 · p. 27
  • SEQ security models uncomputation attacks by permitting query reversal but refusing new queries once one has been recorded, and requires simulation from the SEQ oracle.The oracle uses a compressed random oracle to record queries.Source: §3.5 · p. 28

3.6 qIND-qCPA Secure Secret Key Encryption

  • qIND-qCPA security allows quantum adversaries superposition queries in both learning and challenge phases, using coherent randomness within each query and fresh randomness across queries.Source: §3.6 · pp. 29–30
  • Assuming post-quantum secure pseudorandom permutations, qIND-qCPA-secure secret-key encryption exists.Source: §3.6 · p. 30

4 Generalized One-Time Programs

This section generalizes SEQ-secure one-time program compilers to arbitrary one-time signature token schemes and introduces one-shot programs that support queries on multiple inputs with distinct serial numbers. It establishes security through a sequence of equivalent or indistinguishable hybrids, using techniques including compressed-oracle transformations, cache cancellation, commuting checks, and replacement by the SEQ oracle.

4.1 Definition

  • A generalized one-time program permits one effective query per serial number, preventing two different main inputs from being evaluated under the same serial.The database may record multiple queries, provided their serial numbers are distinct.Source: §4.1 · pp. 30–31

4.2 Construction

  • The construction uses a generalized signature token scheme to compile any randomized function family into a generalized one-time program compiler.The oracle evaluates the function only when supplied a valid signature for the input and serial number; the construction satisfies the compiler definition.Source: §4.2 · p. 32

4.3 One-Time Programs From Any Signature Token

  • Instantiating the construction with any one-time signature token scheme yields a one-time program compiler satisfying syntax, correctness, and SEQ security.Source: §4 · p. 30, §4.3 · p. 34

4.4 One-Shot Programs

  • A one-shot signature scheme in the construction yields a one-shot program compiler, whose evaluator can generate many tokens with unique serial numbers and use each once.The one-shot construction is a generalized one-time program with sk = pk, enabling token generation using the public key.Source: §4.4 · p. 36

4.5 Proof of Security for Generalized OTPs

  • The generalized one-time program construction satisfies the compiler’s SEQ security property.Source: §4.5 · p. 36
  • Hybrids 1 and 2 are perfectly indistinguishable by, lemma 4.Source: §4.5 · p. 38
  • Hybrids 2 and 3 are computationally indistinguishable assuming the one-shot signature scheme is strongly secure.The added SEQ check rules out two different valid message-signature pairs with the same serial number.Source: §4.5 · pp. 39–40
  • Hybrids 3 and 4 are perfectly indistinguishable using an invertible split that separates the database into a smaller register and a cache.The split is invertible, so its unitary implementation permits the transformations in the two hybrids to cancel.Source: §4.5 · pp. 40–41
  • Hybrids 4 and 5 are perfectly indistinguishable even though hybrid 5's compressed database omits signatures.Hybrid 5 changes the compressed-oracle procedures and uses a cache to track signatures; the resulting operations match those in hybrid 4.Source: §4.5 · pp. 42–44
  • Hybrids 4 and 5 perform equivalent operations because their compressed-oracle queries agree on states maintained within span Π_s,x,σ.The SEQ check and compressed-oracle queries preserve that span, which supports the equivalence argument.Source: §4.5 · p. 47
  • Hybrids 5 and 6 are perfectly indistinguishable because the cache steps and compressed-oracle query are rearranged without changing the oracle’s function.The two cache steps in hybrid 6 compute the same function, and the compressed-oracle operation is a notational change.Source: §4.5 · p. 48
  • Hybrids 6 and 7 are computationally indistinguishable because simplifying the SEQ check’s dependence on σ is negligible to distinguish under strong unforgeability.The checks differ only when a database entry shares s and x with the query but has a different σ; detecting this would break strong unforgeability.Source: §4.5 · p. 49
  • Hybrids 7 and 8 are perfectly indistinguishable after the cache steps are moved to run regardless of the control qubit B.Source: §4.5 · pp. 49–50
  • Hybrids 7 and 8 compute equivalent functions regardless of B; when B=|0⟩ at the end of the SEQ check, hybrid 7 applies neither cache, while hybrid 8 applies cache 1 then cache 2, which are inverses.Source: §4.5 · p. 50
  • Hybrids 8 and 9 are perfectly indistinguishable because the cache operation and SEQ check act on separate registers and commute.Reversing their order therefore preserves the computed function.Source: §4.5 · p. 51
  • Hybrids 9 and 10 are perfectly indistinguishable because the SEQ oracle query computes the same function as the replaced check, answer, and uncomputation steps.The SEQ oracle stores the database internally, and the query uses |+⟩ so the bit-flip leaves the control state unchanged.Source: §4.5 · pp. 51–52
  • Hybrids 10 and 11 are perfectly indistinguishable: hybrid 11’s cache 1 operation checks whether condition 11 holds and, if so, modifies C according to hybrid 10’s steps 3a and 3b.Step 3c of hybrid 11 uncomputes step 3a, returning Q′ to its initial state.Source: §4.5 · pp. 52–53
  • Hybrids 1 and 11 are computationally indistinguishable, so any QPT distinguisher has negligible advantage separating the real oracle from the simulator.Hybrid 1 has the real-world oracle distribution, while hybrid 11 is implemented by the simulator.Source: §4.5 · p. 53

5 Query-Limited RAM Programs

Section 5 develops query-limited RAM programs, defining stateful access through a stack-ordered effective-query oracle and giving a compiler for randomized RAM programs. It also establishes cache-based simulations of the one-shot-program SEQ oracle and proves indistinguishability across successive hybrids, including for polynomially many quantum queries.

5 Query-Limited RAM Programs

  • QLPs let a RAM program update its state while ensuring evaluator access remains consistent with the queries made so far.RAM evaluations produce a sequence of memory states, and the access restriction prevents an evaluator from querying a state inconsistent with that sequence.Source: §5 · p. 53

5.1 Definition

  • The LEQ oracle restricts access to the top layer of queries, requiring later queries to be uncomputed before earlier ones can be accessed.Its ancillas preserve a superposition of ordered queries, randomness, and resulting states, enforcing a computation history consistent with the program’s current state.Source: §5.1 · pp. 54–55

5.2 Construction

  • The compiler theorem establishes a query-limited RAM program compiler for any family of randomized RAM programs.Its correctness argument matches one-shot-program outputs to the RAM computation over polynomially many evaluations; the security proof shifts evaluation and state tracking to an SEQ oracle while enforcing contiguous query history.Source: §5.2 · pp. 56–58

5.3 Proof of Security

  • The security proof replaces the one-shot program with a simulator and uses an SEQ-oracle hybrid to establish security against the LEQ oracle.The hybrid moves evaluation and state tracking into the SEQ oracle and limits queries to a new query or a repetition of the most recent one, preventing erasure of older query history without first erasing newer queries.Source: §5.2 · pp. 57–58

5.3.1 Ordering the Database

  • The ordering argument shows that signatures in the SEQ database correspond to the starting state or to a state already recorded there, even if the adversary sees a measured copy of the database.This property allows the database entries to be ordered starting from the initial serial number.Source: §5.3.1 · p. 60
  • After polynomially many queries, the compressed-oracle chaining lemma guarantees a corresponding database entry satisfying condition 6b, except with negligible probability.The argument applies the lemma to the SEQ oracle’s compressed database and the signing oracle.Source: §5.3.1 · p. 62

5.3.2 Simulating the One-Shot Program SEQ Oracle

  • The simulator proof establishes successive hybrid equivalences or computational indistinguishability, including moving signature validation and switching the SEQ check to use the cache.The cited transitions include Hyb0/Hyb1 equivalence, computational indistinguishability to Hyb1, and Hyb7/Hyb6 equivalence.Source: §5.3.2 · pp. 65, 67
  • The SEQ-oracle simulator maintains serial-to-index, input, and output caches to track queries and answer from recorded history.The input cache maps indices to program inputs, while the serial cache maps serial numbers to indices; the construction also uses history and cache checks.Source: §5.3.2 · pp. 64, 67
  • Hyb9 adds an output cache of program-query results, and Hyb10 uses it to answer queries with a serial number inside the recorded sequence without repeating evaluation.The early-answer step applies when the queried serial’s index is below the highest recorded index.Source: §5.3.2 · pp. 68, 69, 71
  • Later hybrids replace database-derived random values with queries to H, remove the history check, and make Hyb13 equivalent to Hyb12 by Claim 5.2.The H-query change is statistically close to Hyb10, and removing the history check is statistically close to Hyb11.Source: §5.3.2 · pp. 69–70
  • Successive hybrids are shown statistically or computationally indistinguishable for the transitions in Claims 5.3–5.6, 5.8–5.10, and 5.12–5.17.The passage says this chain makes Hyb0 indistinguishable, but the supplied text cuts off before stating the comparison target.Source: §5.3.2 · p. 71
  • The history-consistency check fails only negligibly in Hyb2; a noticeable failure would yield a valid signature with no recorded precursor and break DC-Unforg security.The reduction stops before a randomly selected query and outputs the signature and message associated with the missing precursor.Source: §5.3.2 · p. 71
  • In Hyb5, the input-cache invariant makes cached serial/index and partial-input entries correspond exactly to the matching database entry after every query.The proof proceeds by induction over queries and checks cache clearing, evaluation, and cache filling.Source: §5.3.2 · pp. 72–73
  • The simulator maintains an output-cache invariant that tracks program outputs alongside the serial-number and input-cache state.The invariant is stated after every query and relates cache entries to records in the compressed database.Source: §5.3.2 · p. 74
  • The early-answer change from Hyb9 to Hyb10 is statistically indistinguishable, and removing the history check is justified because it fails only negligibly often.The early-answer comparison uses a bound on query-level differences; the history-check removal relies on the negligible failure probability established for the preceding hybrid.Source: §5.3.2 · pp. 78–79

5.3.3 Simulating the Hybrid Oracle

  • The simulated hybrid oracle is indistinguishable from the real hybrid oracle to any distinguisher making polynomially many queries.The distinguisher may have program P hardwired because it is quantified after P.Source: §5.3.3 · p. 79
  • Proposition 2 states that a simulator exists for every RAM program and polynomial-query distinguisher, together with a negligible function.Source: §5.3.3 · p. 79

Hybrids

  • Hybrids 1 and 2 are perfectly indistinguishable after any number of quantum queries.Source: Hybrids · p. 84
  • Hybrids 2 and 3 are perfectly indistinguishable after any number of quantum queries.Source: Hybrids · p. 86
  • Hybrids 3 and 4 are perfectly indistinguishable after any number of quantum queries.The proof establishes this by induction over queries.Source: State Transition Function of Sim · p. 92
  • At each query, the simulator’s internal registers remain in the reachable-state space, and the two hybrids act equivalently on that state.The proof uses these two claims as its inductive invariant.Source: State Transition Function of Sim · p. 92
  • In the analyzed query cases, the hybrids’ operations agree and leave the simulator state in the reachable-state space.The proof compares the hybrid steps with DecompSim and CopySim, including when the query matches the stored sequence.Source: State Transition Function of Sim · pp. 93–94
  • Hybrids 4 and 5 are perfectly indistinguishable after any number of quantum queries, using basis changes on the simulator’s internal registers.The basis change is undetectable to the party querying the simulator.Source: State Transition Function of Sim · pp. 95–96
  • Hybrids 5 and 6 are perfectly indistinguishable after any number of quantum queries.The proof concludes that hybrid 6 and the hybrid oracle O_P^Hyb(1λ) are perfectly indistinguishable, completing Proposition 2.Source: State Transition Function of Sim · pp. 96, 98
  • Hybrid 6’s Decomp operations can be rearranged and canceled, while the equivalent hybrid 5.b reads directly from D instead of using W.The proof further replaces Decomp operations with DecompHyb and CopySim when query validation ensures the required database condition.Source: State Transition Function of Sim · pp. 97–98

A Compressed Oracle Chaining

This section states a strengthened compressed-oracle chaining lemma for a composition of random oracles. Intuitively, a recorded output of H implies that G records a matching input/output pair leading to H’s input.

A Compressed Oracle Chaining

  • The chaining intuition is that if H records an input/output pair, G also records a matching pair that leads to H’s input.Source: A Compressed Oracle Chaining · p. 101
  • The lemma concerns random oracles G and H implemented with compressed oracles, with H taking an input and a component of G’s output.The statement also defines an arbitrary function f and the resulting composed function F_f.Source: A Compressed Oracle Chaining · p. 101
  • The lemma considers an oracle algorithm interacting with F_f up to query t, then measures the internal states of G and H.It defines an event requiring every measured H entry to have a corresponding G entry mapped to its input by f.Source: A Compressed Oracle Chaining · p. 101

A.1 Alternative Representation of the Decompression Function

This appendix section introduces an alternative representation of the compressed-oracle Decomp operation and explains why it matters between repeated queries to the same input.

A.1 Alternative Representation of the Decompression Function

  • The section derives an alternative representation of Decomp, the operation used for compressed oracles.Source: §A.1 · p. 101
  • Between queries to x, the oracle state can have support on databases beyond the recorded database D∪(x,y).A second query to x applies Decomp_x and maps the database register back to |D∪(x,y)⟩.Source: §A.1 · pp. 101–102
  • Despite that intermediate support, G(x) cannot change between queries to x.The alternative representation is relevant when examining the database register without knowing x.Source: §A.1 · p. 102

A.2 Proof

The proof analyzes how compressed-oracle operations affect the event that the two databases contain matching entries. It bounds the contribution of Decomp_G and uses that bound to control the event after repeated queries.

A.2 Proof

  • A query to H preserves the matching-database event when it holds before the query.The queried H input is already matched by an entry in G, so adding the H result leaves the databases valid with respect to the event.Source: §A.2 · p. 103
  • For the Decomp_G analysis, if no unmatched H entries remain, or at least two remain, the event’s cross-projection is zero.When exactly one unmatched entry remains, the queried G cell must supply its match; the proof bounds this case using A and N.Source: §A.2 · p. 104
  • When a>0, the squared operator norm of E Decomp_{G,x_g} E is exactly 2a/N − (a/N)^2; when a=0, the operator is zero.The bound is attained by choosing c_y = 1/√a.Source: §A.2 · p. 104
  • The proof combines the single-query bounds and iterates them from an initial norm of zero to bound the event after t queries.The measured event probability is bounded by the square of the norm; the supplied passage gives an upper bound of 8t² times an incomplete factor.Source: §A.2 · p. 105

B Applications

The applications section presents examples involving both one-shot programs and query-limited programs.

B Applications

B.1 Pay-Per-Use Programs

This section defines pay-per-use programs in terms of effective-query costs and presents a compiler that certifies accumulated cost while preventing further effective evaluations after proving; its proof establishes negligible soundness error for the original game.

B.1 Pay-Per-Use Programs

  • Only queries that remain recorded in the ideal oracle count toward the bill, so a coherently uncomputed query is not charged.The claimed cost is the cumulative cost of prior evaluations; running Prove adds no evaluation cost.Source: §B.1 · pp. 105–106
  • In Prove-mode, the program outputs the current cost with a signature certifying it, then irreversibly enters a halt state that prevents further effective evaluations.The verifier accepts only if the proof establishes that the effective queries encoded by the compiled program have total cost equal to the claim.Source: §B.1 · p. 106
  • The construction is a pay-per-use program compiler for the RAM-program family, using a query-limited compiler, a blind-unforgeable signature scheme, and a pseudorandom function.Theorem B.1 establishes that it satisfies the compiler definition’s correctness, completeness, security, and soundness requirements.Source: §B.1 · p. 107
  • Soundness follows because an accepted incorrect cost would either enable a blind-signature forgery or contradict the final cost fixed by an effective Prove-query.The proof bounds the forgery case by blind-unforgeability; in the other case, the recorded Prove-query signs the current cost and halts the program, fixing the true effective cost.Source: §B.1 · pp. 111–112
  • Both cases occur only with negligible probability in Hybrid 4, and undoing the hybrids changes success probability by at most a negligible amount.Therefore, the original game's soundness error is negligible.Source: §B.1 · p. 112

B.2 Semi-Quantum Query-Limited Programs

Semi-quantum QLPs let program control pass between users through classical communication while preserving the program’s stateful, query-limited evaluation. The compiler achieves correctness and security even when evaluations and transfers are interleaved.

B.2 Semi-Quantum Query-Limited Programs

  • A semi-quantum QLP extends a regular QLP with an interactive Transfer protocol that lets a sender pass evaluation ability to a receiver using only classical communication.The construction keeps its one-shot program token quantum; the other listed program components are classical strings.Source: §B.2 · pp. 112–113
  • Classical communication transfers evaluation power: the sender’s token is consumed, the receiver gains a usable token, and the hidden RAM state remains unchanged.The transfer protocol runs in Transfer mode, which outputs ⊥.Source: §B.2 · pp. 113–114
  • Theorem B.2 establishes that the Figure 16 construction is a semi-quantum query-limited program compiler for P.Its security proof reduces to regular QLP security by treating the construction as a regular QLP for a two-mode program; the oracle simulator perfectly emulates that program’s queries.Source: §B.2 · p. 114, §1 · p. 118
  • Correctness requires statistically close real- and ideal-world outputs for any operation sequence, including sequences that interleave evaluations with transfers.Transfer-mode outputs are ⊥, and the transfer itself leaves the RAM state unchanged.Source: §B.2 · pp. 112, 114, 116

B.3 One-Shot Signatures Based On Any Blind-Unforgeable Signature Scheme

This section gives a generic construction of one-shot signatures from any blind-unforgeable signature scheme, with verification inherited from the underlying scheme. It proves correctness and unforgeability using a hybrid argument that bounds a QPT adversary’s success negligibly.

B.3 One-Shot Signatures Based On Any Blind-Unforgeable Signature Scheme

  • Earlier one-shot signature constructions produced signatures restricted to vectors in a subspace coset.The section states that this format limitation is not essential.Source: §B.3 · pp. 118–119
  • Any blind-unforgeable signature scheme yields a one-shot signature scheme whose verification applies the underlying scheme’s verification function.The proof approach is similar to, who constructed one-time signatures from any blind-unforgeable signature scheme.Source: §B.3 · p. 119
  • Unlike the one-shot signature notion in definitions 3.4 and 3.6, Definition B.3 guarantees regular rather than strong unforgeability.Regular unforgeability rules out valid signatures on two different messages sharing a serial number; strong unforgeability also rules out two different valid signatures for one serial-number/message pair.Source: §B.3 · p. 119
  • The construction uses a one-shot program for BUS.Sign, and its verifier applies BUS.Ver to an augmented tuple containing the serial number and message.Security intuition is that valid message-signature pairs correspond to queried serial-number/message inputs, while the one-shot program prevents multiple queries with the same serial number.Source: §B.3 · pp. 119–120
  • Theorem B.3 establishes that the construction is a one-shot signature scheme satisfying correctness and regular unforgeability.Correctness follows from OSP correctness, BUS correctness, and PRF pseudorandomness; unforgeability follows from the proof in Lemma B.8.Source: §B.3 · pp. 120, 123
  • Replacing the PRF with a random oracle changes success negligibly, compressed-oracle implementation preserves it exactly, and the database check changes it negligibly.These are the transitions from Hybrid 7 to 8, 8 to 9, and 9 to 10, respectively.Source: §B.3 · pp. 126, 127, 129
  • With t polynomially many complete SEQ calls, the chained-oracle condition holds with squared norm at least 1 − 8t^2/2^λ, so the Hybrid 10 database check passes overwhelmingly.The condition requires every H1 database entry to have a matching H entry; each complete SEQ call includes computation and uncomputation.Source: §B.3 · pp. 128–129
  • For distinct messages, the two H1 equality checks succeed with probability at most 2/2^ℓ ≤ 2^(1−λ), making Hybrid 10’s acceptance probability negligible.The argument uses ℓ ≥ λ, where ℓ is the bitlength of a tuple (s,m,r).Source: §B.3 · pp. 129, 131
  • The previous claims imply negligible success in the unforgeability game, establishing that the OSS scheme is unforgeable.Source: §B.3 · p. 131
Loading 2609.40194v1…