CryptoDB
On Valiant’s Conjecture: Impossibility of Incrementally Verifiable Computation from Random Oracles
| Authors: |
|
|---|---|
| Download: |
|
| Presentation: | Slides |
| Conference: | EUROCRYPT 2023 |
| Abstract: | In his landmark paper at TCC 2008 Paul Valiant introduced the notion of ``incrementally verifiable computation'' which enables a prover to incrementally compute a succinct proof of correct execution of a (potentially) long running process. The paper later won the 2019 TCC test of time award. The construction was proven secure in the random oracle model without any further computational assumptions. However, the overall proof was given using a non-standard version of the random-oracle methodology where sometimes the hash function is a random oracle and sometimes it has a short description as a circuit. Valiant clearly noted that this model is non-standard, but conjectured that the standard random oracle methodology would not suffice. This conjecture has been open for 14 years. We prove that if the proof system can receive a long witness as input in an incremental manner and is also zero-knowledge then the conjecture is true. Valiant's original construction does not have these properties but can easily be extended to have them in his model. We relate our result to recent possibility and impossibility results for SNARKs and incrementally verifiable computation. |
BibTeX
@inproceedings{eurocrypt-2023-32964,
title={On Valiant’s Conjecture: Impossibility of Incrementally Verifiable Computation from Random Oracles},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-30617-4_15},
author={Jesper Buus Nielsen and Mathias Hall-Andersen},
year=2023
}