Delegating computation: interactive proofs for muggles

By Shafi Goldwasser, Yael Tauman Kalai, Guy N. Rothblum. 2008

749 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Geometry and Topology, Algorithms & Complexity

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

In Geometry and Topology

In Algorithms & Complexity

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “[40] and has been studied under various terms in the literature: checking computations [40], certified computation [295], delegating computations [185], as well as verifiable computing [173].”
Bulletproofs: Short Proofs for Confidential Transactions and More (2018, methodology): “Wahby [46] recently present a cryptographic zero-knowledge proof system which achieves square root verifier complexity and proof size based on the proofs for muggles [47] techniques in combination with a sub-linear polynomial commitment scheme.”
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.”
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, background): “[20] (GKR), which draw on many techniques from the PCP literature.”
Verifying computations with state (2013, background): “The client could use a tailored solution [8, 13, 18, 28, 39, 58, 70, 73, 75], but such solutions are not available for all applications.”
Taking Proof-Based Verified Computation a Few Steps Closer to Practicality (2012, background): “[31], and a follow-up effort studies a GPU-based parallel implementation [53].”
How to Delegate and Verify in Public: Verifiable Computation from Attribute-based Encryption (2012, background): “Similar to the noninteractive solution of Goldwasser et al. [14], the effort required to verify results from memory delegation is proportional to the depth of the computation's circuit, which for certain functions may be proportional to the circuit size (e.g., exponentiation).”
Scalable, transparent, and post-quantum secure computational integrity (2018, background): “[58] Shafi Goldwasser, Yael Tauman Kalai, and Guy N.”
Efficient RAM and control flow in verifiable outsourced computation (2015, background): “However, Buffet itself and many of the prior systems (including BCTV, Pantry, and Pinocchio [62]) handle a more general problem—a zero-knowledge proof of knowledge [21, 40]—in which the prover can supply inputs to the computation and keep them private (for example, a private database for which the…”
SafetyNets: Verifiable Execution of Deep Neural Networks on an Untrusted Cloud (2017, methodology): “Existing IP systems proposed in literature [5, 9, 17, 18] use, at their heart, a protocol referred to as the sum-check protocol [13] that we describe here in some detail, and then discuss its applicability in verifying general-purpose computations expressed as arithmetic circuits.”
A Survey of Verifiable Computation (2017, methodology): “Goldwasser, Kalai and Rothblum [39] presented a publicly delegable verifiable computation protocol for functions that can be computed by circuits of size poly ( n ) and depth poly ( log ( n )), where poly ( n ) denotes an un-specified function f ( n ) = o ( n c ) for some constant c > 0.”
Time-Optimal Interactive Proofs for Circuit Evaluation (2013, methodology): “We describe a refinement of a powerful interactive proof protocol due to Goldwasser, Kalai, and Rothblum [20].”