Verifying computations without reexecuting them

By Michael Walfish, Andrew Justin Blumberg. 2015

190 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

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, methodology): “The core idea behind Prio is reminiscent of techniques used in verifiable computation [16, 37, 62, 69, 97, 115, 116, 119], but in reverse—the client proves to a set of servers that it computed a function correctly.”
SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud (2017, background): “ystems (and, indeed, all existing VC techniques) when used for verifying general-purpose computations is that the prover’s overheads are large, often orders of magnitude more than just computing f(x) [19]. Recently, however, Thaler [17] showed that certain types of computations admit IP protocols wi”
The Efficient Server Audit Problem, Deduplicated Re-execution, and the Web (2017, background): “A possibility is probabilistic proofs [20, 23, 32, 65, 75, 89], but they cannot handle our workloads, so we would have to estimate, and the estimates would yield outlandish speedups for OROCHI (over 106×).”
Homomorphic Encryption (2017, background): “, [90] for a survey (focusing on the practical-oriented side of that work).”
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (2017, background): “The last half decade has seen tremendous progress in designing and implementing e cient systems for veri able computation (see [4, 47] for recent surveys).”
A scalable verification solution for blockchains (2019, background): “In comparison with other proposed blockchain-based computation systems, or even PCP-based verifiable computing systems [65], the work imposed on the Judges by the verification game is small [12], as is the computational overhead required to join the system [63].”
The relationship between trust in AI and trustworthy machine learning technologies (2019, background): “nance data [27, 90] and cryptographic solutions to verify model’s behaviours without exposing user privacy [72] or revealing model‘s intellectual properties [87].”
Transparent SNARKs from DARK Compilers (2020, background): “In recent years, there has been a surge of industry interest in verifiable outsourced computation [52] (such as trustless cloud computing) as well as zeroknowledge proofs.”