Incrementally Verifiable Oracle Aided Computation
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.
Nadia: We're looking at the paper: "Incrementally Verifiable Oracle Aided Computation".
Elias: Here's the gist of the paper. 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.
Nadia: This is crucial for AI safety applications where systems interact over time and perform subsequent computations.
Elias: The paper extends IVC to oracle-aided computations, modeling external information access as oracle queries, requiring certification of consistency with the underlying oracle.
Nadia: Efficient verification demands that the verifier makes substantially fewer oracle queries than those made by the computation being verified.
Paper summary: Nadia: So, to wrap up what we've just heard about "Incrementally Verifiable Oracle Aided Computation," the main thesis is that we can build short proofs for computations where the prover keeps adding steps without redoing all previous work.
Elias: This is crucial for AI safety because AI systems are interactive, meaning they perform many steps after every interaction, and we need a way to verify that sequence incrementally.
Priya: They extend existing succinct non-interactive arguments, SNARGs, into this incremental setting by assuming the Learning with Errors assumption.
Nadia: And they tackle two distinct environments: robust computations where the oracle might be unreliable in some cases, and signed oracles where the oracle access is authenticated.
Elias: In the robust case, they create privately verifiable SNARGs and IVC schemes that work even for non-deterministic computations, provided every incorrect execution on a false input yields at least an epsilon fraction of incorrect oracle answers.
Priya: The private verification keys and proofs in this robust setting are polynomial in lambda, S, log T, and one over epsilon <ref:2611.14698#pg2>.
Nadia: And the verification itself requires O lambda over epsilon oracle calls to ensure soundness for those robust claims. That's a specific number they have to satisfy.
Elias: For signed oracles, they achieve publicly verifiable SNARGs and IVC without needing that robustness assumption at all, which means an oracle-free setup and verification.
Priya: So the paper shows two different ways to handle the challenge: private verification with a few queries for robust cases, and public verification with zero queries for signed cases.
Nadia: It really boils down to: robustness enables succinct incremental verification of unauthenticated oracle computations using private keys and a small number of oracle calls.
Elias: And signed oracles enable public, oracle-free verification even when the underlying computation isn't robust.
Conclusion: Nadia: Looking at the whole paper, "Incrementally Verifiable Oracle Aided Computation," we see they are providing tools for verifying complex, sequential computations that rely on external information.
Elias: The authors tackle this by separating the problem into two clear scenarios: robust computations and signed oracles.
Priya: It’s interesting how they use the hash-and-BARG paradigm with local extraction in the robust setting, and adapt techniques from established methods for signed oracles.
Nadia: The key finding is that robustness enables succinct incremental verification of unauthenticated oracle computations using private verification and a small number of oracle queries.
Elias: For signed oracles, they show that computations with access to signed oracles admit publicly verifiable SNARGs and IVC under the Learning with Errors assumption, and this setup requires no robustness assumption at all.
Priya: The overall implication is that we can now build verification systems that keep up with dynamic AI interactions while being sensitive to whether the information coming from an oracle is trustworthy.
Nadia: The work extends existing IVC schemes by making them work for oracle-aided computations, which directly addresses a real need in AI safety where systems are constantly computing and interacting.
Elias: The paper confirms that the IVC construction for signed oracles is publicly verifiable, while the construction for robust computations is privately verifiable.
Priya: The efficiency bounds they state are polynomial in lambda, S, and log T, which suggests these schemes are computationally feasible given reasonable security parameters.
Nadia: So we have methods to verify these time- T, space- S oracle-aided computations efficiently, whether the oracle is robust or signed.
Elias: The title "Incrementally Verifiable Oracle Aided Computation" highlights that the core contribution is linking incremental proof maintenance with the need to handle external information access in a practical way.
Shafi Goldwasser, Yael Tauman Kalai
MIT · RESI
cs.CR
Submitted: 2026-11-10
Updated: 2026-11-10
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 100/100
The gist: 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…
Key concepts
- Incrementally Verifiable Computation (IVC)
- IVC lets a prover create a proof that can be efficiently updated after every computation step. This is vital when systems perform many sequential operations, as the proof remains short and doesn't need to store the entire history of previous calculations.
- Robust Computations
- This setting applies when computations might involve external oracle answers that are slightly incorrect (at least an epsilon fraction of them). The paper constructs schemes that can still provide a reliable, verifiable proof even when some oracle responses are faulty.
- Signed Oracles
- In this setting, the external information provided to the computation is cryptographically signed. This allows for constructions that are publicly verifiable and require no oracle queries from the verifier during checking.
- Oracle-Aided Computation
- This refers to computations where the system can access external, pre-computed information or answers through specific queries (oracles). The goal is to verify these complex processes efficiently while accounting for this external data access.
Terminology
Summary
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. p. 0 Incrementally Verifiable Oracle Aided Computation
Shafi Goldwasser∗ Yael Tauman Kalai†
November 13, 2026
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. In the context of AI safety, the need for incremental verification
is particularly important, as AI systems interact with users over time and perform further
computation after each interaction. In the context of AI safety, the need for incremental verification
is particularly important, as AI systems interact with users over time and perform further
computation after each interaction. However, standard IVC schemes do not directly address a
crucial feature of AI tasks: their dependence on external information and expertise. As emphasized by the UK AISI Alignment Team [IM25], 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. 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?Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
The paper constructs IVC schemes under two main settings: Robust computations and Signed oracles. p. 0 We construct IVC schemes for oracle-aided computations under the Learning with Errors
(LWE) assumption by first constructing succinct non-interactive arguments (SNARGs), and then
extending them to the incremental setting. We consider the following two settings, where below,
λ is the security parameter, n is the input length, and T, S, and Q are the time, space, and
oracle-query bounds.Where the paper says it
For Robust computations, including non-deterministic ones, where every accepting execution on a false input yields at least an epsilon-fraction of incorrect oracle answers, privately verifiable SNARGs and IVC are constructed. The public parameters, private verification keys, and proofs have length polynomial in (lambda, S, T, 1/epsilon), and verification requires O(lambda/epsilon) oracle calls. p. 0 For IVC, the corresponding robustness condition is imposed on the claimed configuration. Public parameters, private verification keys, and proofs have length poly(λ, S, log T, 1/ε),
and verification uses O(λ/ε) oracle calls. 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.Where the paper says it
Where the paper says it
For Signed oracles, publicly verifiable SNARGs and IVC are constructed without a robustness assumption, featuring an oracle-free setup and verification.
The paper presents two complementary possibilities: 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. p. 3 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. 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.Where the paper says it
Where the paper says it
Theorem 1 (Robust oracle-aided computation) asserts that assuming sub-exponential hardness of LWE, there exist a privately verifiable SNARG and a privately verifiable IVC scheme for every time- T, space- S oracle-aided computation, including non-deterministic computations. p. 3 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-T,
space-S oracle-aided computation, including non-deterministic computations. Assuming sub-exponential hardness of
LWE, there exist a privately verifiable SNARG and a privately verifiable IVC scheme for every time-T,
space-S oracle-aided computation, including non-deterministic computations. Both schemes satisfy
adaptive completeness and, for ε-robust claims, adaptive soundness, with the following guarantees:
• The public parameters, private verification key, and proof have length poly(λ, S, log T, 1/ε).Where the paper says it
Where the paper says it
Theorem 3 (Signed oracle-aided computation) states that computations with access to signed oracles admit publicly verifiable SNARGs and IVC under LWE assumptions. p. 5 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. 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.Where the paper says it
Where the paper says it
The constructions utilize the hash-and-BARG paradigm with local extraction in the robust setting, and adapt established techniques in the signed-oracle setting. p. 7 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. • Each IVC proof update and verification takes time poly(n, λ, S, log T, 1/ε). • The prover updates its proof after each step without access to the private verification key or
the preceding execution history. 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.Where the paper says it
Where the paper says it
Where the paper says it
The paper details specific algorithms:
-
Privately verifiable IVC for robust computations (Definition 40): This scheme uses an updatable hash family HT with local openings, OrdIVC for ordinary intervals, and an updatable batch argument UpBARG. The maintained proof consists of a hash of the sequence of query-answer pairs (Z 1,, Z q), a UpBARG proof (pi h,i) certifying that these queries are in L block and satisfy consistency conditions under crsh i, an ordinary-IVC proof eta, and the last record D last. p. 8
The verification algorithm IVC. p. 0Where the paper says it
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); for T polynomially bounded in λ, polynomial hardness of LWE suffices.
V checks configuration consistency, parsed records, and UpBARG statements using extracted witnesses from td. p. 8Where the paper says it
Incrementally Verifiable Oracle Aided Computation Shafi Goldwasser∗ Yael Tauman Kalai† November 13, 2026 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. In the context of AI safety, the need for incremental verification is particularly important, as AI systems interact with users over time and perform further computation after each interaction.
The verifier makes at most r = O(lambda/epsilon) oracle calls. p. 2Where the paper says it
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.
Where the paper says it
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.
-
Publicly verifiable IVC for signed oracles (Definition 39): This scheme is based on two independent UpBARG instances to facilitate the soundness proof, resulting in publicly verifiable IVC with efficiency bounds poly(lambda, S, T). The verifier makes no oracle calls. p. 2
Where the paper says it
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.
The final results confirm that the IVC construction for signed-oracles is publicly verifiable, while the construction for robust computations is privately verifiable. p. 6 Section 5 constructs privately verifiable
SNARGs for robust computations, and Section 6 proves the lower bound for deterministic public
verification. Section 7 develops publicly verifiable SNARGs for signed oracles, including the fully
succinct deterministic construction. 3), and the corresponding IVC
refinement appears at the end of Section 8. For larger deterministic time bounds, the constructions
require correspondingly stronger, poly(T)-hard security; polynomial hardness alone is not sufficient
for that extension. The space-dependent constructions
assume sub-exponential hardness of LWE; for deterministic signed-oracle computations with T
polynomially bounded in λ, polynomial hardness suffices. Throughout this overview, T and S denote the time and space bounds, n is the input length,
and λ is the security parameter.Where the paper says it
Where the paper says it
Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Robust computation verification allows AI systems to maintain a short proof of correctness even when interacting with an external oracle whose answers might be incorrect on at least an epsilon fraction of calls, without needing a private verification key or recomputing preceding steps.
-
Signed oracle models enable publicly verifiable succinct non-interactive arguments and IVC without any robustness assumption, allowing AI safety auditors to independently check the computation's correctness using only public parameters and no oracle queries during verification.
-
The IVC construction for signed oracles allows an AI system to maintain an incrementally verifiable proof of its state after each interaction, where the verifier checks that the next configuration is reachable from the previous one according to a relation that includes a digital signature check on every oracle transition.
-
For deterministic computations with short oracle queries and answers, publicly verifiable SNARGs allow for verification in time n times poly(lambda, log T) by removing dependence on space bounds S, significantly speeding up audits for fixed-query-count tasks.
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.
Sources
Related papers
- From Strategy Search to Policy Learning: MCTS-Guided Adversarial Co-Evolution for LLM Safety Alignment
- Privacy Leakage from Recurrent State in LLM Inference
- Privilege and confidentiality in generative AI workflows
- BadMoE: Backdooring Mixture-of-Experts LLMs via Routing-Aware Triggers and Task-Underutilized Experts
- CoVault: Secure, Scalable Analytics of Personal Data
- Honeyval: A Comprehensive Evaluation Framework for LLM-powered HTTP Honeypots