Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
By Paul Valiant. 2008
245 citations recorded by the source corpus.
Subfields: Artificial Intelligence, Computational Theory and Mathematics
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Artificial Intelligence
- Dan Boneh
- Eli Ben-Sasson
- Srinath T. V. Setty
- Eran Tromer
- Alessandro Chiesa
- Michael Riabzev
- Michael Walfish
- Madars Virza
In Computational Theory and Mathematics
- Eli Ben-Sasson
- Dan Boneh
- Eran Tromer
- Michael Riabzev
- Alessandro Chiesa
- Iddo Bentov
- Madars Virza
- Michael Naehrig
Citations in the corpus
- Geppetto: Versatile Verifiable Computation (2015, methodology): “Our full paper [23] formalizes this process, adapting the usual proof-ofa-proof bootstrapping techniques [11, 53].”
- Formalizing Human Ingenuity: A Quantitative Framework for Copyright Law's Substantial Similarity (2022, methodology): “Furthermore, using incrementally-verifiable computation [12, 13, 94], the time to produce the proofs is linear in running time of P and R.”
- Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, methodology): “Two other important differences are: (i) proofs in SCI are not zero-knowledge whereas prior solutions are, and (ii) the setup of SCI is not only shorter but also Table 1: Quantitative comparison of SCI with KOE-based [BCG + 13a] and IVC-based [BCTV14a] solutions.”
- Scalable, transparent, and post-quantum secure computational integrity (2018, methodology): “• Incrementally Verifiable Computation (IVC): This approach, suggested by Valiant [105] (cf. [39, 29]) reduces prover space consumption by relying on knowledge extraction assumptions; this approach can be applied on top of other proof systems with succinct (sub-linear) verifiers, including ZK-STARK,”
- Quadratic Span Programs and Succinct NIZKs without PCPs (2013, background): “The systems we discuss here are based on non-falsifiable assumptions [9, 12, 32, 36, 38, 47] or are not robust [2, 17, 24].”
- Scalable Zero Knowledge Via Cycles of Elliptic Curves (2014, methodology): “This formulation includes as special cases incrementally-verifiable computation [109] and targeted malleability”
- Verifiable Delay Functions (2018, methodology): “IVC was first studied by Valiant [70] in the context of computationally sound proofs [54].”