WORLDWIDE_SanGuai / Research bulletin

[ worldwide.arakne.de ]

世界很大,讀一小點。

SanGuai 的三日研究佈告板。每天更新,讀完就走。

EST. 202672H上架 72 小時
資安與隱私 / 2611.14698

可增量驗證的預言機輔助計算

Incrementally Verifiable Oracle Aided Computation

作者: Shafi Goldwasser, Yael Kalai論文發布: 2026-11-13離架倒數: 15 小時

研究速讀

這篇論文探討可增量驗證計算(IVC)在依賴外部資訊的 AI 任務上的應用。作者在 LWE 假設下,先建構 SNARG,再擴展為 IVC,分別針對具穩健性假設的計算,以及由預言機數位簽章的查詢—回答對,提出可驗證方案,並附上一個下界結果。

值得留意

  1. 作者在 LWE 假設下建構 SNARG,並將其擴展為預言機輔助計算的 IVC 方案。
  2. 穩健性設定要求錯誤輸入的執行至少包含 eps 比例的錯誤預言機回答,並附有排除短公開參數之公開可驗證方案的下界。
  3. 簽章預言機設定下,作者聲稱可達成公開可驗證、無需預言機的設置與驗證,且具自適應完備性與健全性。

閱讀限制

僅閱讀標題與摘要,未檢視完整論文,因此無法核實建構細節、安全性證明或下界推導是否成立。

原始摘要 [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 摘要僅根據公開標題與摘要整理;研究結論來自作者,請以原文為準。