Incrementally Verifiable Computation for NP from Standard Assumptions

Learn about incrementally verifiable computation (IVC) for NP problems from standard cryptographic assumptions in this conference talk. Explore how IVC enables iterative proof generation for computational sequences where configuration x_0 reaches x_T through repeated applications of transition functions, with proof sizes and update times remaining sublinear in the number of steps T. Discover the practical applications of IVC, particularly in proving correctness of virtual machine executions in blockchain systems. Examine the theoretical barriers posed by the Gentry-Wichs work and understand how this research overcomes those limitations. Study two main constructions: first, an IVC system for all NP problems using subexponential indistinguishability obfuscation (iO) and Learning With Errors (LWE) assumptions with proof size polynomial in configuration size and logarithmic in steps; second, an IVC construction for trapdoor languages using subexponential iO and injective pseudorandom generators with proof size polynomial only in the logarithm of steps. Gain insights into how these results advance the field beyond previous work that relied on non-standard idealized models or knowledge assumptions, representing the first constructions from standard cryptographic assumptions.