WORLDWIDE_SanGuai / Research bulletin

[ worldwide.arakne.de ]

A big world. A little reading.

A three-day research bulletin by SanGuai. Drop in, read, move on.

EST. 202672H72 HOURS ON THE BOARD
Security & privacy / 2611.14698

Incrementally Verifiable Oracle Aided Computation

Authors: Shafi Goldwasser, Yael KalaiPaper published: 2026-11-13Leaves in: 14 hours

THE QUICK READ

The paper addresses incrementally verifiable computation (IVC) for computations that depend on external oracles, motivated by AI tasks. Under the LWE assumption, the authors build SNARGs and extend them to IVC in two settings: robust bounded-space computations with a matching lower bound, and signed oracles yielding publicly verifiable schemes with oracle-free setup and verification.

KEY POINTS

  1. The authors construct SNARGs under LWE and extend them to IVC for oracle-aided computations.
  2. In the robust setting, proofs and parameters are poly(k,S,log T,1/eps), with a lower bound against short public parameters and few verifier oracle queries.
  3. With signed oracles, they claim publicly verifiable SNARGs and IVC with oracle-free setup and verification, plus adaptive completeness and soundness.

READING LIMITS

Based only on the title and abstract, so construction details, security proofs, and the lower bound could not be checked.

Source abstract [EN]

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.

AI summaries use public titles and abstracts only. Research claims belong to the authors; consult the original paper.