CryptoDB
Incrementally Verifiable Computation for NP from Standard Assumptions
| Authors: |
|
|---|---|
| Download: | |
| Conference: | CRYPTO 2025 |
| Abstract: | Incrementally verifiable computation (IVC) [Valiant, TCC'08] allows one to iteratively prove that a configuration $x_0$ reaches another configuration $x_T$ after repeated applications of a (possibly non-deterministic) transition function $\mathcal{M}$. The key requirement is that the size of the proof and the time to update the proof is sublinear in the number of steps $T$. IVC has numerous applications such as proving correctness of virtual machine executions in blockchains. Currently, IVC for $\mathsf{NP}$ is only known to exist in idealized models, or based on knowledge assumptions. No constructions are known from standard assumptions, or even in the random oracle model. Furthermore, as observed in prior works, since IVC for $\mathsf{NP}$ implies adaptive succinct non-interactive arguments for $\mathsf{NP}$, the work of Gentry-Wichs [STOC `11] seemingly poses barriers to constructing IVC for $\mathsf{NP}$ from falsifiable assumptions. In this work, we observe that the Gentry-Wichs barrier can be overcome for IVC for NP. We show the following two results: * Assuming subexponential $i\mathcal{O}$ and LWE (or bilinear maps), we construct IVC for all $\mathsf{NP}$ with proof size $\mathsf{poly}(|x_i|,\log T)$. * Assuming subexponential $i\mathcal{O}$ and injective PRGs, we construct IVC for \emph{trapdoor IVC languages} where the proof-size is $\mathsf{poly}(\log T)$. Informally, an IVC language has a trapdoor if there {\em exists} a (not necessarily easy to find) polynomial-sized circuit that determines if a configuration $x_i$ is reachable from $x_0$ in $i$ steps. |
BibTeX
@inproceedings{crypto-2025-35751,
title={Incrementally Verifiable Computation for NP from Standard Assumptions},
publisher={Springer-Verlag},
author={Pratish Datta and Abhishek Jain and Zhengzhong Jin and Alexis Korb and Surya Mathialagan and Amit Sahai},
year=2025
}