Making argument systems for outsourced computation practical (sometimes)

By Srinath T. V. Setty, Richard McPherson, Andrew Justin Blumberg, Michael Walfish. 2012

188 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Geppetto: Versatile Verifiable Computation (2015, background): “Prior work on verifying computation focused on narrow classes of computation [32, 51], relied on physical-security assumptions [41, 47], assumed uncorrelated failures [19, 20], or achieved good asymptotics [2, 28, 30, 31, 33, 38, 44] but impractical concrete performance [46, 50].”
Pinocchio: Nearly Practical Verifiable Computation (2013, methodology): “Setty et al. produced a second line of PCP-based systems called Pepper [27] and Ginger [28].”
Machine Unlearning (2019, background): “Thus, understanding if the unlearning procedure can be veriﬁed , similar to approaches in other domains [52]–[54], is of merit.”
Verifying computations with state (2013, background): “, see [45] for partial surveys of this literature).”
Taking Proof-Based Verified Computation a Few Steps Closer to Practicality (2012, methodology): “V sends (Enc(pk, r), pk) to P.”
Verifying computations without reexecuting them (2015, methodology): “Pepper [42] and Ginger [43] reﬁne the protocol of IKO.”
ALITHEIA: Towards Practical Verifiable Graph Processing (2014, methodology): “A VC protocol for graph algorithms can be derived in theory via black-box use of existing general-purpose VC schemes [18, 14, 24, 9, 10, 19, 11], or one of the systems that have been built to apply these techniques [33, 32, 30, 7, 12, 36].”
Ligero: Lightweight Sublinear Arguments Without a Trusted Setup (2017, background): “Linear PCPs are simpler to construct than classical PCPs and have served as the basis for some of the rst implementations of veri able computation protocols [43].”
A Hybrid Architecture for Interactive Verifiable Computation (2013, background): “…− 1 is the sum of the outputs of gates g2, g3 at layer i; it returns 0 otherwise. multi(g1, g2, g3) is analogous but returns 1 when g1 at layer i − 1 is the prod- where the only wires in the circuit connect adjacent layers (versus skipping over them). uct of the outputs of gates g2, g3 at layer i.”
Efficient RAM and control flow in verifiable outsourced computation (2015, background): “Buffet allows the programmer to express programs in an expansive subset of C (disallowing only “goto” and function pointers), can handle essentially any example in the verifiable computation literature, and achieves the best performance in the area by multiple orders of magnitude.”
Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs (2019, background): “N on -i nt er ac ti ve Classical (MA) [8] Read all Read all PCP [6,7] Read all Point Kilian [65], Micali [71] Linear PCP [60] Read all Linear IKO [60], Pepper [82], GGPR [51], PHGR [76,77], BCIOP [25]”
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×).”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, methodology): “Thus, the first works with an explicit motivation to build “practical” systems using probabilistic proofs [40, 80, 82, 83, 86] refine and implement simple interactive protocols of Ishai et al.”
Quadratic Span Programs and Succinct NIZKs without PCPs (2013, background): “(See [46] for an implementation of IKO that claims a factor of 1017 improvement over a naive implementation of IKO, yet still finds the prover complexity prohibitive in general, and therefore constructs more efficient PCPs for specific functions such as matrix multiplication.”
Verifiable differential privacy (2015, background): “Another line of work [41–43, 47] combines the interactive arguments of Ishai et al.”