Resolving the conflict between generality and plausibility in verified computation

By Srinath T. V. Setty, Benjamin Braun, Victor Vu, Andrew Justin Blumberg, Bryan Parno, Michael Walfish. 2013

157 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

In Computational Theory and Mathematics

Citations in the corpus

Geppetto: Versatile Verifiable Computation (2015, methodology): “A recent system, Pantry [16], implements such collision-resistant hashing on top of the existing QAP-based Pinocchio [46] and Zaatar protocols [49].”
Pinocchio: Nearly Practical Verifiable Computation (2013, methodology): “Previous systems either did not offer a compiler [25–27], or compiled from a subset of an academic language, SFDL [28, 60].”
Verifying computations with state (2013, methodology): “To briefly compare the performance of Zaatar and Pinocchio, Pinocchio has superior amortization behavior (see above) but higher proving and setup costs (and hence higher cross-over points), by constant factors.”
Verifiable ASICs (2016, background): “We discuss non-recurring costs (engineering, creating photolithographic masks, etc.) in Section 9.”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, methodology): “If we define the G-gate to be a multiplication gate, so that degG = 2, then the construction of Theorem 11 matches the complexity of the GGPR-based linear PCP [51,81] and provides what is essentially an alternative formulation of that proof system.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “Zaatar [81] leverages this observation to build an interactive argument with O(n log n) asymptotics for the prover by composing a QAP-based linear PCP with a refined variant of IKO’s cryptographic machinery [82, 83].”
Verifying computations without reexecuting them (2015, methodology): “5Systems that report verification costs beating local execution choose very expensive baselines for local computation [36, 41–43].”
Verifiable differential privacy (2015, background): “Another line of work [41–43, 47] combines the interactive arguments of Ishai et al.”
Time-Optimal Interactive Proofs for Circuit Evaluation (2013, methodology): “They also 1 http://aws.amazon.com/elasticmapreduce/ build a hybrid system that statically evaluates whether it is better to use the GKR protocol or a different, cryptography-based argument system called Zaatar (see Section 1.1), and runs the more efficient of the two protocols in an automated fashio”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, unknown): “KOE-based systems were implemented in [66, 71, 15, 19, 77], and further optimizations of this latter system for specific applications related to Bitcoin [65] such as smart contracts [58] and anonymous payment systems [12] are already being evaluated by commercial entities [46].”
Efficient RAM and control flow in verifiable outsourced computation (2015, methodology): “The principal costs are the setup work and the prover’s work to generate the certificate.”
A Survey of Verifiable Computation (2017, methodology): “Setty et al. addressed this issue in their paper [61].”
Full Accounting for Verifiable Outsourcing (2017, background): “The front-end transforms Ψ from its original expression to an AC, denoted C; this step often uses a compiler [19, 22, 31, 32, 37, 45, 66, 73, 75, 81, 84], though is sometimes done manually [18, 36, 77].”
Scalable Zero Knowledge with No Trusted Setup (2019, methodology): “The first implementation of a QSP based system is called Pinocchio [63], with subsequent implementations including libSNARK [19, 68] which is used in the Zerocash and ZcashTM implementations; additional implementations appear in [70, 73, 72, 71, 24, 79, 37, 82].”