betaFeedback

WorksComputer Science

Incrementally Verifiable Oracle Aided Computation

Abstract

Incrementally verifiable computation (IVC) allows a prover to maintain a short proof that can be efficiently updated after each computation step, without retaining or recomputing the preceding execution. Standard IVC schemes do not directly address a crucial feature of AI tasks: their dependence on external information and expertise. We construct IVC schemes for oracle-aided computations under the LWE assumption by first constructing SNARGs, and then extending them to IVC. We consider the following two settings, where below, k is the security parameter, n is the input length, and T, S, and Q are the time, space, and oracle-query bounds. 1. Robust computations: For bounded-space computations, including non-deterministic computations, in which every accepting purported execution on a false input contains at least an eps-fraction of incorrect oracle answers, we construct privately verifiable SNARGs and IVC. Public parameters, private verification keys, and proofs have length poly(k ,S, log T,1/eps), and verification uses O(k/eps) oracle calls. We complement this result with a lower bound ruling out (deterministic) publicly verifiable SNARGs and IVCs with public parameters of length o(n), and o(Q) verifier oracle queries. 2. Signed oracles: For oracles that digitally sign their query-answer pairs, we construct publicly verifiable SNARGs and IVC without a robustness assumption, and with oracle-free setup and verification. Public parameters and proofs have length poly(k,S,log T). For deterministic computations with oracle query and answer lengths poly(k,log T), we remove the dependence on S, obtaining public parameter and proof lengths poly(k,log T). All our constructions have adaptive completeness and soundness.

Introduction

Incrementally verifiable computation (IVC) [21] allows a computation to maintain a short proof of the computation performed so far. After each step, the prover updates a succinct proof certifying the current configuration, without retaining or recomputing the preceding execution. IVC is particularly relevant to the way we use AI systems: we interact with them over time, providing new inputs and receiving responses as a conversation or task unfolds. Each new interaction prompts further computation that builds on the system’s current state. The computation thus proceeds incrementally, and we would like verification to proceed alongside it.

Several IVC schemes have been proposed in the literature, including schemes based on standard cryptographic assumptions such as LWE [19, 9, 20]. These results, however, do not directly address an important feature of many AI tasks: their dependence on external information and expertise. As emphasized by the UK AISI Alignment Team [13], verification methods for AI safety should accommodate access to external information and human judgment. Oracle-aided computation provides a natural model for such computations: an AI system may query an external database, consult a specialized service, or ask for human judgment, with each consultation represented by an oracle query. Extending IVC to this setting requires certifying that the computation is consistent with the underlying oracle. Moreover, efficient verification requires the verifier to make substantially fewer oracle queries than made by the computations they verify. Combining these two goals leads to the question at the center of this work:

Can an oracle-aided computation maintain a short, efficiently updatable proof of its correctness that can be verified using few oracle queries?

Oracle access introduces a fundamental obstacle to constructing succinct proofs that can be verified using few oracle queries, even for a single computation. As was observed by Barbara, Chiesa, and Guan [3], for an arbitrary computation, one incorrect answer can change the outcome while leaving all ordinary transitions valid. A verifier that makes substantially fewer oracle queries than the computation may fail to inspect precisely that answer. Barbara et al. prove that relativized succinct arguments, where the verifier makes a sublinear number of oracle calls, do not exist, even with interaction and computational soundness.

We study two approaches to overcoming this obstacle. In both settings, our constructions satisfy adaptive completeness and soundness: completeness holds even when the input and honest execution are chosen after seeing the public parameters, and soundness holds even when a cheating prover chooses its claim after seeing these parameters.

  • The first approach follows Chen, Kalai, and Xi [7] and restricts soundness to robust computations, in which an incorrect conclusion requires a substantial fraction of the oracle answers to be wrong. Chen et al. showed that this robustness condition enables doubly-efficient interactive verification. We construct non-interactive succinct arguments (SNARGs) and then extend them to IVC for robust oracle-aided bounded-space computations, including non-deterministic computations, under the sub-exponential hardness of LWE. Our schemes are privately verifiable. Namely, checking a proof requires a secret verification key generated during setup and withheld from the prover, who can construct and update proofs without access to this key. We complement this result with a lower bound: for general robust oracle-aided computations, a SNARG or IVC scheme with oracle-free setup and adaptive completeness and soundness cannot have both public parameters of length sublinear in the input length and a

deterministic public verifier making a number of oracle queries sublinear in the computation’s query count.

  • We would nevertheless like to obtain publicly verifiable SNARGs and IVC. For AI oversight, we want a proof to serve as a certificate that can be shared and independently checked by users, auditors, and other systems, without access to a private verification key. Our second approach makes this possible by requiring the oracle to authenticate its responses. Specifically, a signed oracle attaches a digital signature to each query-answer pair. This is a natural requirement when the oracle represents an external database or service: its provider can sign responses as they are issued, making their authenticity publicly checkable. We show that signed oracles enable publicly verifiable SNARGs and IVC under LWE assumptions. Signing the oracle’s responses also removes the robustness restriction altogether: our constructions apply to arbitrary computations with access to signed oracles, even when a single incorrect oracle answer can change the outcome. Moreover, verification requires no oracle queries.

Taken together, our results delineate two complementary possibilities for incrementally verifiable oracle-aided computation. Robustness enables succinct incremental verification of unauthenticated oracle computations using private verification and a small number of oracle queries; signed oracles enable public, oracle-free verification even for non-robust computations. The main technical innovations of this work lie in the robust setting, where we develop new techniques for proving soundness and preserving it under incremental proof updates. The signed-oracle constructions build on established techniques; their contribution is primarily conceptual, showing that authenticating oracle responses enables publicly verifiable SNARGs and IVC without any robustness requirement.

Our Results in More Detail

Throughout this work, we denote by λ\lambda the security parameter, nn the input length, and TT, SS, and QQ the time, space, and oracle-query bounds. The underlying oracle is fixed independently of setup, and setup makes no oracle queries. Our constructions have adaptive completeness and soundness: in particular, an adversary may choose its statement and proof after seeing the public parameters. All cryptographic assumptions are required to hold even given access to the underlying oracle.

Robust computations: from interaction to SNARGs and IVC. A purported execution follows the machine’s transition rules but may use incorrect oracle answers. We say that a computation is ε\varepsilon-robust on an input if the input is accepting, or every accepting purported execution uses incorrect answers on at least an ε\varepsilon-fraction of its oracle calls. Given a complete accepting purported execution on a false robust input, a verifier could detect an incorrect oracle answer by checking a small random sample of its oracle calls. Our first result obtains this guarantee using a SNARG and preserves it under incremental proof updates.

Theorem 1 (Robust oracle-aided computation, informal). Assuming sub-exponential hardness of LWE, there exist a privately verifiable SNARG and a privately verifiable IVC scheme for every time-TT, space-SS oracle-aided computation, including non-deterministic computations. Both schemes satisfy adaptive completeness and, for ε\varepsilon-robust claims, adaptive soundness, with the following guarantees:

  • The public parameters, private verification key, and proof have length poly⁡(λ,S,log⁡T,1/ε)\operatorname{poly}(\lambda, S, \log T, 1/\varepsilon).

  • The verifier makes O(λ/ε)O(\lambda/\varepsilon) oracle queries.

  • Each IVC proof update and verification takes time poly⁡(n,λ,S,log⁡T,1/ε)\operatorname{poly}(n, \lambda, S, \log T, 1/\varepsilon).

  • The prover updates its proof after each step without access to the private verification key or the preceding execution history.3

Here, adaptive completeness allows the input and honest execution to be chosen after seeing the public parameters. Adaptive soundness guarantees that no efficient adversary, given these parameters, can produce an accepting proof of a false ε\varepsilon-robust claim except with negligible probability. For IVC, robustness is imposed on the configuration being certified: every purported execution reaching an incorrect claimed configuration must contain an ε\varepsilon-fraction of incorrect oracle answers. Robustness of the final output alone does not imply this property for every intermediate configuration. It does imply the required condition for an accepting terminal configuration on a robust false input. The formal SNARG and IVC results appear in Theorem 20 (Section 5) and Theorem 49 (§ 7.5), respectively. § 3.2.1 and § 3.3.1 give the corresponding overviews.

A barrier to deterministic public verification. The private verification key conceals which oracle answers will be checked. The following theorem rules out deterministic public verification with short public parameters and few oracle queries.

Theorem 2 (Public-verification lower bound, informal). There does not exist a non-interactive argument for general robust oracle-aided computations with oracle-free setup, adaptive completeness and soundness, public parameters of length o(n)o(n), and a deterministic public verifier making o(Q)o(Q) oracle queries. This holds even for deterministic computations making nonadaptive oracle queries, and regardless of the proof length. The same impossibility applies to IVC with these guarantees.

The negative result already holds for the simple computation that, on input xx, makes the QQ oracle queries (x,1),…,(x,Q)(x,1),\ldots,(x,Q) and outputs the majority of the resulting bits. For every candidate SNARG, our proof constructs an oracle, fixed independently of setup, and a cheating prover that produces an accepting proof of a false robust claim with non-negligible probability over the public parameters. Thus, under these requirements, robustness alone does not suffice for deterministic public verification. The IVC consequence follows by considering the proof at termination. See Theorem 24 (§ 6) and the overview in § 3.3.

Public verification through signed oracles. For many applications, we would like a certificate that anyone can verify, without a private verification key or further access to the external sources. A result might be checked by several auditors, passed to another computation, or verified after the original oracle is no longer available. We also want to support computations that depend critically on individual oracle answers and therefore need not be robust.

Our second approach is to require the oracle to authenticate its answers. A signed oracle, on query uu, returns the answer a=O(u)a = O(u) together with a digital signature on the pair (u,a)(u,a). The oracle holds the signing key, and its verification key is public and authenticated. An external database or service can therefore make its responses verifiable by signing them when they are supplied. For a versioned database, the version identifier can be included in the query. The answers themselves can be arbitrary; no randomness or algebraic structure is required. Signatures have previously been used in oracle-assisted proof systems, beginning with Chiesa and Tromer [8]. Here they authenticate the external information on which the application’s computation depends. Independently of our work, Chiesa, Guan, and Yıldız [5] also study signed application oracles in the context of zero-knowledge verification. Our signed-oracle results provide succinct non-interactive and incremental verification under LWE.

Theorem 3 (Signed oracle-aided computation, informal). Computations with access to signed oracles admit publicly verifiable SNARGs and IVC, with adaptive completeness and adaptive soundness, under the assumptions below. No robustness assumption is required, and neither setup nor verification makes oracle queries.

  • For time-TT, space-SS non-deterministic computations, sub-exponential hardness of LWE suffices. Public parameters and proofs have length poly⁡(λ,S,log⁡T)\operatorname{poly}(\lambda, S, \log T), and IVC proof updates and verification take time poly⁡(n,λ,S,log⁡T)\operatorname{poly}(n, \lambda, S, \log T).

  • For deterministic time-TT computations with oracle queries and answers of length poly⁡(λ,log⁡T)\operatorname{poly}(\lambda, \log T), sub-exponential hardness of LWE suffices. Public parameters and proofs have length poly⁡(λ,log⁡T)\operatorname{poly}(\lambda, \log T), and verification and IVC proof updates take time n⋅poly⁡(λ,log⁡T)n \cdot\operatorname{poly}(\lambda, \log T). When TT is polynomially bounded in λ\lambda, polynomial hardness of LWE suffices.

The hardness assumptions are understood to hold even given access to the underlying oracle. The honest prover obtains only the authenticated oracle responses used by the underlying execution.

The bounded-space results appear in Theorem 27 (Section 7) and Theorem 45 (§ 7.4). The fully succinct deterministic SNARG is Theorem 31 (§ 6.5), and the corresponding IVC refinement appears at the end of § 7.4. For larger deterministic time bounds, the constructions require correspondingly stronger, poly⁡(T)\operatorname{poly}(T)-hard security; polynomial hardness alone is not sufficient for that extension. § 3.1 gives an overview of both constructions.

The contribution of this approach is primarily conceptual: authenticating external answers makes public succinct and incremental verification possible even when an individual answer can determine the outcome. The constructions adapt established hash-and-batch-argument and updatable-batch-argument techniques, with local checks for signatures. Their soundness uses local extraction to turn an incorrect authenticated answer into a signature forgery. In particular, the verifier checks a succinct proof of the authenticated execution; it need not receive and verify every signature separately.

Related Work

Oracle-aided verification and AI oversight. The study of oracle-aided verification is motivated in part by approaches to AI oversight in which a verifier has limited access to external information or judgment. Irving, Christiano, and Amodei [12] proposed AI safety via debate, and Brown-Cohen, Irving, and Piliouras [4] developed doubly-efficient debate protocols. These models use competing provers. Chen, Kalai, and Xi [7] study single-prover verification and obtain doubly-efficient interactive proofs and arguments for robust computations and for computations with low-degree oracles. In particular, their robust interactive argument uses O(1/ε)O(1/\varepsilon) verifier oracle queries for constant soundness error. We study non-interactive arguments and incremental proof maintenance for bounded-space computations, and show a further limitation on deterministic public verification even under robustness.

Signed oracle models. Chiesa and Tromer [8] introduced a signed-input-and-randomness functionality and used it to construct short non-interactive arguments and proof-carrying data. The functionality supplies signed randomness to support extraction and recursive proof composition; their verifier already operates without access to it. They also discuss realizations using signature cards and trusted services. Maller, Mohnblatt, and Zapico [18] introduce the open-and-sign random-oracle model to obtain security guarantees for recursive proof systems, including IVC of polynomial depth. These works concern oracle functionalities used by the proof system itself. Our setting authenticates arbitrary answers supplied by the application’s external sources.

Independent work of Chiesa, Guan, and Yıldız [5] also considers this use of signed oracle answers. They study zero knowledge for oracle-aided computations, prove an impossibility result in the random-oracle model, and obtain zero-knowledge verification with efficient prover and verifier for signed oracles under collision-resistant hashing. Our work focuses on succinct non-interactive arguments and IVC under LWE, with the time–space bounds stated above, and also treats robust computations with unsigned oracles.

Succinct arguments from standard assumptions. Our constructions build on the development of batch arguments and SNARGs from standard cryptographic assumptions. Choudhuri, Jain, and Jin [6] construct SNARGs for deterministic polynomial-time computations from LWE. Kalai, Vaikuntanathan, and Zhang [15] obtain SNARGs for bounded-space non-deterministic computations under sub-exponential LWE. Our bounded-space signed-oracle result preserves the polynomial dependence on space and polylogarithmic dependence on time available for oracle-free NTISP(TT, SS). The additional issue is establishing that locally extracted oracle responses agree with the underlying oracle, using either signature unforgeability or the quantitative guarantee supplied by robustness.

Incrementally verifiable computation. IVC originates in the work of Valiant [21]. Chiesa and Tromer [8] introduced proof-carrying data, and Bitansky, Canetti, Chiesa, and Tromer [2] developed recursive composition and bootstrapping for SNARKs and proof-carrying data. Paneth and Pass [19] and, independently, Devadas, Goyal, Kalai, and Vaikuntanathan [9] obtain IVC for deterministic computations from LWE using rate-1 batch arguments.

Our incremental constructions use the updatable batch arguments of Aldema Tshuva and Oshman [20], who develop a general framework for lifting delegation schemes to IVC across several models of computation. Their primitive supports adding statements and witnesses as they become available. We use this framework to maintain local certificates of an oracle-aided execution. In the robust setting, the additional challenge is to preserve hidden sampling and quantitative soundness for a growing sequence of unauthenticated oracle responses.

Paper Organization

§ 3 gives a technical overview. § 4 reviews the cryptographic primitives, and § 5 defines robust oracle-aided computation and its verification. Section 5 constructs privately verifiable SNARGs for robust computations, and § 6 proves the lower bound for deterministic public verification. Section 7 develops publicly verifiable SNARGs for signed oracles, including the fully succinct deterministic construction. § 7 defines oracle-aided IVC and gives constructions in both settings.

Technical Overview

Technical Overview

The main difficulty in constructing SNARGs and IVC for oracle-aided computations is certifying the correctness of the oracle answers. Although numerous techniques are known for standard computations, both deterministic and non-deterministic, the oracle-aided setting presents a fundamental barrier. As observed in prior work [3], a cheating prover can honestly execute a computation with respect to an oracle that differs from the true oracle on a single query. This single discrepancy may change the outcome, yet the verifier can detect it only by querying the oracle at that point. Thus, without further restrictions, the verifier may need to check every oracle answer, undermining our goal of making verification substantially more efficient than the computation itself.

We overcome this barrier in two settings. First, we consider signed oracles, whose answers come with signatures authenticating the query-answer pairs. We incorporate signature verification into the computation being proved and use local extraction to establish soundness. This yields publicly verifiable SNARGs and IVC for arbitrary oracle-aided computations, with a verifier that makes no oracle queries. We describe this approach in § 3.1.

Second, we consider arbitrary oracles but require soundness only for robust computations: for any input xx and any incorrect claimed output yy, every purported execution4 on xx that outputs yy must contain a substantial fraction of incorrect oracle answers. With this relaxed soundness guarantee, we obtain SNARGs and IVC with relatively few verifier oracle queries. Our SNARGs and IVC in this setting are privately verifiable. We describe this approach in § 3.2. In § 3.3, we rule out deterministic publicly verifiable SNARGs and IVC with a sublinear number of oracle queries and public parameters of length o(n)o(n).

We begin with the signed-oracle setting, whose analysis is simpler and serves as an introduction to our approach. Our main technical innovations arise in the robust setting. Our constructions follow the hash-and-BARG paradigm with local extraction, and we prove soundness under the LWE assumption. The key is to show that local guarantees suffice to establish the correctness of the oracle answers. For signed oracles, we adapt the local-extraction analysis to recover a signature forgery from a false proof. For arbitrary oracles, we show that the verifier’s hidden oracle checks reject an incorrect claim with high probability whenever every purported execution supporting that claim contains a substantial fraction of incorrect oracle answers. The space-dependent constructions assume sub-exponential hardness of LWE; for deterministic signed-oracle computations with TT polynomially bounded in λ\lambda, polynomial hardness suffices.

Throughout this overview, TT and SS denote the time and space bounds, nn is the input length, and λ\lambda is the security parameter. The oracle is fixed independently of setup, and our cryptographic assumptions are required to hold even for adversaries with access to it.

Signed Oracles

A signed oracle returns an answer a=O(u)a = \mathcal{O}(u) together with a signature on (u,a)(u,a). Its verification key vk is public and known to both the prover and the verifier, while its signing key is known only to the oracle. We first explain how to use these signatures to construct a SNARG, and then how to maintain the proof incrementally.

From signed answers to a SNARG

We begin with non-deterministic computations running in time TT and space SS. Our first construction has proof and public parameter lengths poly⁡(λ,S,log⁡T)\operatorname{poly}(\lambda, S, \log T) and relies on sub-exponential hardness of LWE. This matches the best known dependence on the time and space bounds for oracle-free SNARGs for NTISP(T,ST, S) from LWE. We later show how to remove the dependence on the space bound for deterministic computations.

We follow the hash-and-BARG approach with local extraction, used in prior LWE-based SNARG constructions for NTISP [15, 6]. The prover hashes the computation and uses a batch argument to certify its local transitions. We augment these transitions with signature verification and rely on the local-extraction guarantees. Here it is essential to recover the signature itself: a valid signature on an incorrect oracle answer may exist, so ordinary soundness for the augmented computation does not suffice. Local extraction allows us to turn a false proof into an explicit signature forgery.

Soundness. Our analysis follows the local-extraction approach of prior work. We track whether a configuration is reachable at the prescribed time using correct oracle answers. The initial configuration is reachable, whereas an accepting configuration on a false input is not. A transition from a reachable configuration to an unreachable one must therefore either violate the machine’s transition rules or use an incorrect oracle answer. The former violates the batch argument’s local-extraction guarantee. In the latter case, the extracted witness contains a valid signature on an incorrect query-answer pair, yielding a signature forgery.

To formalize this intuition, we use two independent batch-argument components to extract neighboring transitions. Collision resistance ensures that their shared configuration agrees, while index hiding allows us to move the extraction indices through the computation. Tracking reachability across these comparisons connects the prescribed initial configuration to the claimed endpoint. Consequently, a successful cheating prover allows us to break one of the underlying primitives or forge a signature.

Removing the space dependence. For deterministic computations, we can remove the dependence on the space bound using techniques from prior work. We compress configurations by replacing the work tape with its Merkle-tree hash. Authentication paths allow us to check the symbols read by each transition and the resulting change to the tape hash using a short witness. The local-extraction guarantee of the batch argument allows the soundness reduction to recover a signature on an incorrect oracle answer. Moreover, the soundness analysis can compare extracted configurations with the unique execution under the true oracle, avoiding the need to explore the bounded-space configuration graph. For IVC, we additionally use an updatable hash family to authenticate the growing sequence of transition records without rehashing the preceding records. For short oracle queries and answers, this yields proof and public parameter lengths poly⁡(λ,log⁡T)\operatorname{poly}(\lambda, \log T); for TT polynomially bounded in λ\lambda, polynomial hardness of LWE suffices.

Making the proof incremental

Our IVC construction follows the same approach, using the updatable batch arguments of Aldema Tshuva and Oshman [20]. These allow the prover to extend its proof after each computation step without revisiting the preceding execution. As above, we apply this machinery to a computation that also verifies signatures on its oracle query–answer pairs. The soundness analysis adapts the same local-extraction argument, with signature unforgeability ruling out incorrect oracle answers. This yields publicly verifiable IVC with proof and public parameter lengths poly⁡(λ,S,log⁡T)\operatorname{poly}(\lambda, S, \log T) and a verifier that makes no oracle queries. For deterministic computations with short oracle queries and answers, the same configuration compression removes the dependence on SS.

Robust Computations

We next consider arbitrary oracles, whose answers need not carry signatures. Here robustness provides another way to check correctness: on a false input, every accepting purported execution contains at least an ε\varepsilon fraction of incorrect oracle answers. If we could inspect such an execution, checking a few randomly chosen oracle answers would therefore suffice. Our goal is to obtain the same guarantee from a succinct proof.

A privately verifiable SNARG

We again use hash-and-BARG with local extraction, but now give the verifier private extraction trapdoors. These allow it to recover selected query-answer pairs and check them against the true oracle. We append a table listing all oracle calls to the computation transcript, and use the batch argument to certify that each table entry agrees with the corresponding call in the transcript. This allows the verifier to sample uniformly from the oracle calls.

Soundness. For signed oracles, extracting one incorrect answer together with its signature suffices to obtain a contradiction. For arbitrary oracles, we need a quantitative guarantee: the verifier’s hidden checks must detect incorrect answers with sufficient probability.

If the proof specified a complete purported execution, this would follow immediately from robustness. However, local extraction only gives witnesses for selected positions, and we cannot assume that these witnesses come from a single, globally consistent execution. Moreover, the prover chooses its input and proof after seeing the public parameters.

We address this using a potential Φtx(C)\Phi_t^x(C): the minimum number of incorrect oracle answers needed to reach configuration CC at time tt on input xx, over all purported executions. We cap this quantity at QQ, the number of oracle calls in every purported execution. The potential is used only in the analysis; the verifier does not compute it.

A correct transition cannot increase the potential, and an incorrect oracle answer can increase it by at most one. The potential starts at zero, while robustness guarantees that it is at least εQ\varepsilon Q at any accepting configuration on a false robust input. Along a single execution, these properties would imply at least εQ\varepsilon Q incorrect answers. Our argument obtains an analogous bound in expectation from local extractions that need not form a single execution.

More precisely, let psp_s be the probability that the prover outputs a false robust instance, all public checks accept, and the first ss private checks accept. We show that, for each check except the last,

ps≤(1−ε)ps−1+negl⁡(λ).p_s \le(1-\varepsilon)p_{s-1}+\operatorname{negl}(\lambda).

Although the hidden indices are sampled independently, the prover chooses its input and proof after seeing the public parameters, which are generated using these indices. Thus, this bound does not follow from independence alone.

To account for the preceding checks, let EE be the event defining ps−1p_{s-1}. We multiply each potential by 1E\mathbf{1}_E before taking expectations, so outcomes outside EE contribute zero.5 We compare neighboring local extractions using the current component and the last component, whose trapdoor is unused by the preceding checks. Index hiding lets us change one component’s extraction index while evaluating the weighted potential with the other component’s trapdoor. When both components open the same transcript position, hash binding ensures that they recover the same configuration, except with negligible probability. We can therefore switch which component evaluates the potential and continue changing indices.

These comparisons allow the expected weighted potential differences to telescope. The initial-to-final potential gap then gives a lower bound on the contribution of incorrect oracle answers. Relating these answers to the oracle-call table and averaging over its entries yields

Pr⁡[E and the sth private check rejects]≥εps−1−negl⁡(λ),\Pr[E \text{ and the }s\text{th private check rejects}] \ge\varepsilon p_{s-1} - \operatorname{negl}(\lambda),

which implies the desired recurrence. Iterating it over all but the last check gives negligible soundness error with O(λ/ε)O(\lambda/\varepsilon) oracle queries, without extracting a complete execution.

Impossibility of succinct deterministic public verification

We show that robustness alone does not suffice for deterministic public verification with a sublinear number of oracle queries and short public parameters. Specifically, there is no publicly verifiable SNARG for general robust oracle-aided computations with oracle-free setup, adaptive completeness and soundness, public parameters of length o(n)o(n), and a deterministic verifier making o(Q)o(Q) oracle queries. Here nn is the input length and QQ is the number of oracle calls made by the computation.

Our counterexample is a simple majority computation. Consider a Boolean oracle whose queries are pairs (x,i)(x,i), where x∈{0,1}nx \in\{0,1\}^n and i∈[Q]i \in[Q]. We view the oracle as a table: each input xx indexes a row consisting of the QQ bits O(x,1),…,O(x,Q)\mathcal{O}(x,1),\ldots,\mathcal{O}(x,Q). On input xx, the computation reads this row and outputs its majority:

O(x)=Maj⁡(O(x,1),…,O(x,Q)).\mathcal{O}(x)=\operatorname{Maj}(\mathcal{O}(x,1),\ldots,\mathcal{O}(x,Q)).

For intuition, fix the public parameters and an accepting proof for some input under the all-one oracle. A deterministic verifier making only ℓ=o(Q)\ell=o(Q) oracle queries examines very few entries of the input’s row. Preserve those entries and change the remaining entries of that row to zero. Every answer seen by the verifier remains unchanged, so it still accepts. However, the row now contains at most ℓ\ell ones, making the claimed majority incorrect. Moreover, any accepting purported execution must use incorrect answers on a constant fraction of its oracle calls. Thus, the false claim satisfies the robustness requirement.

The difficulty is that the oracle must be fixed before the public parameters are generated. We use the shortness of the public parameters to encode every possible parameter string crs\mathsf{crs} as a distinct input xcrsx_{\mathsf{crs}}. For each such string, we simulate the honest prover and verifier under the all-one oracle and identify the entries of row xcrsx_{\mathsf{crs}} queried by the verifier. This allows us to specify the corresponding row for every possible crs\mathsf{crs} in advance. After setup, the cheating prover chooses the input xcrsx_{\mathsf{crs}} and supplies the corresponding proof.

We cannot simply modify all these rows: the verifier may also query rows other than the one indexed by its input, and changing those rows could change its verification decision. Instead, we modify only a sparse set of rows, selected using a pairwise-independent hash function. With non-negligible probability, the row xcrsx_{\mathrm{crs}} is modified while every other row visited by the verifier is left unchanged. On this event, the verifier sees exactly the same answers as under the all-one oracle and accepts a false robust claim. An averaging argument fixes the row selection and the prover’s randomness before setup, yielding a single oracle for which the attack succeeds with non-negligible probability over the public parameters.

The argument places no restriction on the proof length. Thus, the lower bound holds even for non-succinct non-interactive arguments with these parameter and query bounds. The same impossibility applies to IVC, since its proof at termination would give a SNARG for the completed computation. The formal result appears in § 6.

Making the proof incremental

To obtain IVC, we must maintain this ability to sample oracle calls as the computation grows. We separate ordinary computation from oracle calls: an ordinary IVC certifies the computation between consecutive calls, while an outer updatable batch argument aggregates one record per oracle call. This lets the prover update its proof after every computation step while allowing the verifier to sample oracle calls directly.

A further issue is that the number of oracle calls in the claimed execution is not known at setup. Sampling from the full query bound could miss a much shorter execution. We therefore prepare hidden samples for query-count ranges whose sizes are powers of two. Verification uses a range within a factor of two of the claimed number of calls, preserving the sampling guarantee with only logarithmic overhead.

The same analysis extends to IVC by evaluating the potential at oracle-call boundaries. Soundness of the ordinary IVC ensures that the intervening computation cannot increase the potential, while the consistency guarantees of the updatable batch argument connect neighboring records. Thus, the quantitative argument continues to apply as the computation grows.

Under sub-exponential hardness of LWE, both constructions have proof and public parameter lengths poly⁡(λ,S,log⁡T,1/ε)\operatorname{poly}(\lambda, S, \log T, 1/\varepsilon). Verification uses O(λ/ε)O(\lambda/\varepsilon) oracle queries, and IVC updates require no access to the private verification key.

Preliminaries

Notation. We let λ\lambda denote the security parameter throughout the paper. We use PPT to denote probabilistic polynomial-time, and denote the set of all positive integers up to nn as [n]:={1,…,n}[n] := \{1,\ldots,n\}. For any x∈{0,1}nx \in\{0,1\}^{n} and any subset J⊆[n]J \subseteq[n] we denote by xJ=(xj)j∈Jx_J = (x_j)_{j \in J}. For any finite set SS, x←Sx \mathrel{\leftarrow} S denotes a uniformly random element xx from the set SS. Similarly, for any distribution D\mathcal{D}, x←Dx \mathrel{\leftarrow} \mathcal{D} denotes an element xx drawn from the distribution D\mathcal{D}.

Hash Families with Local Opening and Updatability

In this section we recall the definition of a hash family with local opening [16]. These preliminaries are due to [BBK^{+}23].

Syntax. A hash family (HT) with succinct local opening consists of the following algorithms:

Gen⁡(1λ)→hk\operatorname{Gen}(1^\lambda) \to\mathsf{hk}. This is a PPT algorithm that takes as input the security parameter λ\lambda in unary and outputs a hash key hk\mathsf{hk}.

Hash⁡(hk,x)→rt\operatorname{Hash}(\mathsf{hk},x) \to\mathsf{rt}. This is a deterministic poly-time algorithm that takes as input a hash key hk\mathsf{hk} and an input x∈{0,1}Nx \in\{0,1\}^{N} for N≤2λN \le2^\lambda, and outputs a hash value rt\mathsf{rt}.

Open⁡(hk,x,j)→ρ\operatorname{Open}(\mathsf{hk},x,j) \to\rho. This is a deterministic poly-time algorithm that takes as input a hash key hk\mathsf{hk}, an input x∈{0,1}Nx \in\{0,1\}^{N} for N≤2λN \le2^\lambda, and an index j∈[N]j \in[N], and outputs an opening ρ\rho.

Verify⁡(hk,rt,j,b,ρ)→0/1\operatorname{Verify}(\mathsf{hk},\mathsf{rt},j,b,\rho) \to0/1. This is a deterministic poly-time algorithm that takes as input a hash key hk\mathsf{hk}, a hash value rt\mathsf{rt}, an index j∈[N]j \in[N], a bit b∈{0,1}b \in\{0,1\} and an opening ρ\rho. It outputs 1 (accept) or 0 (reject).

References

  1. [1][BBK+23] Zvika Brakerski, Maya Farber Brodsky, Yael Tauman Kalai, Alex Lombardi, and Omer Paneth. SNARGs for monotone policy batch NP. In Helena Handschuh and Anna LysyansKaya, editors, CRYPTO 2023, Part II, volume 14082 of LNCS, pages 252–283. Springer, Heidelberg, August 2023. 10, 13DOI
  2. [2][BCCT13] Nir Bitansky, Ran Canetti, Alessandro Chiesa, and Eran Tromer. Recursive composition and bootstrapping for SNARKS and proof-carrying data. In Dan Boneh, Tim Roughgarden, and Joan Feigenbaum, editors, 45th ACM STOC, pages 111–120. ACM Press, June 2013. 5, 13
  3. [3][BCG24] Annalisa Barbara, Alessandro Chiesa, and Ziyi Guan. Relativized succinct arguments in the ROM do not exist. Cryptology ePrint Archive, Paper 2024/728, 2024. 1, 6DOI
  4. [4][BCIP24] Jonah Brown-Cohen, Geoffrey Irving, and Georgios Piliouras. Scalable AI safety via doubly-efficient debate. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 4585–4602. PMLR, 2024. 4
  5. [5][CGY26] Alessandro Chiesa, Ziyi Guan, and Burcu Yıldız. Can AI oversight be zero knowledge? Cryptology ePrint Archive, Paper 2026/2299, 2026. 4, 5arxiv.org/abs/2610.01995
  6. [6][CJJ22] Arka Rai Choudhuri, Abhishek Jain, and Zhengzhong Jin. SNARGs for 𝒫 from LWE. In 62nd FOCS, pages 68–79. IEEE Computer Society Press, February 2022. 5, 7, 13, 15
  7. [7][CKX26] Liyan Chen, Yael Tauman Kalai, and Zoe Xi. How to avoid debate: Scalable AI safety via doubly-efficient interactive proofs. In Proceedings of the 43rd International Conference on Machine Learning, volume 306 of Proceedings of Machine Learning Research, pages 14831–14858. PMLR, 2026. 1, 4arxiv.org/abs/2607.03561
  8. [8][CT10] Alessandro Chiesa and Eran Tromer. Proof-carrying data and hearsay arguments from signature cards. In Proceedings of the 1st Symposium on Innovations in Computer Science (ICS 2010), pages 310–331. Tsinghua University Press, 2010. 4, 5
  9. [9][DGKV22] Lalita Devadas, Rishab Goyal, Yael Kalai, and Vinod Vaikuntanathan. Rate-1 non-interactive arguments for batch-NP and applications. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1057–1068. IEEE Computer Society, 2022. Full version: Cryptology ePrint Archive, Report 2022/1236. 1, 5DOI
  10. [10][GW11] Craig Gentry and Daniel Wichs. Separating succinct non-interactive arguments from all falsifiable assumptions. In Lance Fortnow and Salil P. Vadhan, editors, 43rd ACM STOC, pages 99–108. ACM Press, June 2011. 13
  11. [11][HJKS22] James Hulett, Ruta Jawale, Dakshita Khurana, and Akshayaram Srinivasan. SNARGs for P from sub-exponential DDH and QR. In Orr Dunkelman and Stefan Dziembowski, editors, EUROCRYPT 2022, Part II, volume 13276 of LNCS, pages 520–549. Springer, Heidelberg, May / June 2022. 15DOI
  12. [12][ICA18] Geoffrey Irving, Paul Christiano, and Dario Amodei. AI safety via debate. arXiv:1805.00899, 2018. 4arxiv.org/abs/1805.00899
  13. [13][IM25] Geoffrey Irving and Simon Marshall. The need to relativise in debate. AI Alignment Forum, June 2025. UK AISI Alignment Team: Debate Sequence. 1
  14. [14][KLVW23] Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Daniel Wichs. Boosting batch arguments and RAM delegation. In Barna Saha and Rocco A. Servedio, editors, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, STOC 2023, Orlando, FL, USA, June 20–23, 2023, pages 1545–1552. ACM, 2023. 13, 15DOI
  15. [15][KVZ21] Yael Tauman Kalai, Vinod Vaikuntanathan, and Rachel Yun Zhang. Somewhere statistical soundness, post-quantum security, and SNARGs. In Kobbi Nissim and Brent Waters, editors, TCC 2021, Part I, volume 13042 of LNCS, pages 330–368. Springer, Heidelberg, November 2021. 5, 7, 13DOI
  16. [16][Mer88] Ralph C. Merkle. A digital signature based on a conventional encryption function. In Carl Pomerance, editor, CRYPTO’87, volume 293 of LNCS, pages 369–378. Springer, Heidelberg, August 1988. 10, 11DOI
  17. [17][Mic94] Silvio Micali. CS proofs (extended abstracts). In 35th FOCS, pages 436–453. IEEE Computer Society Press, November 1994. 13
  18. [18][MMZ25] Mary Maller, Nicolas Mohnblatt, and Arantxa Zapico. IVC in the open-and-sign random oracle model. Cryptology ePrint Archive, Paper 2025/1663, 2025. ASIACRYPT 2025. 5DOI
  19. [19][PP22] Omer Paneth and Rafael Pass. Incrementally verifiable computation via rate-1 batch arguments. In 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 1045–1056. IEEE Computer Society, 2022. Full version: Cryptology ePrint Archive, Report 2023/1394. 1, 5DOI
  20. [20][TO26] Eden Aldema Tshuva and Rotem Oshman. Model-generic incrementally verifiable computation from updatable bargs. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 6:1–6:22. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2026. 1, 5, 7, 11, 12, 43, 44, 46DOI
  21. [21][Val08] Paul Valiant. Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In Theory of Cryptography Conference (TCC 2008), volume 4948 of Lecture Notes in Computer Science, pages 1–18. Springer, 2008. 1, 5DOI
  22. [22][WW22] Brent Waters and David J. Wu. Batch arguments for sfNP and more from standard bilinear group assumptions. In Yevgeniy Dodis and Thomas Shrimpton, editors, CRYPTO 2022, Part II, volume 13508 of LNCS, pages 433–463. Springer, Heidelberg, August 2022. 15DOI

Paper details

vlnc:W_4jzzb9ku
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 14

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

generative AI tools

View statement
Looking for related papers…
Contents