Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

By Rosario Gennaro, Craig Gentry, Bryan Parno. 2010

1,221 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Information Systems, Program Analysis & Verification, Privacy & Security

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

1. Dan Boneh
2. Srinath T. V. Setty
3. Michael Walfish
4. Eli Ben-Sasson
5. Justin Thaler
6. Andrew Justin Blumberg
7. Eran Tromer
8. Craig Gentry

In Information Systems

1. Dan Boneh
2. Brent Waters
3. Craig Gentry
4. Jonathan Katz
5. Srinath T. V. Setty
6. Rosario Gennaro
7. Eli Ben-Sasson
8. Matthew D. Green

In Program Analysis & Verification

1. Srinath T. V. Setty
2. Michael Walfish
3. Andrew Justin Blumberg
4. Eli Ben-Sasson
5. Justin Thaler
6. Eran Tromer
7. Alessandro Chiesa
8. Charalampos Papamanthou

In Privacy & Security

1. Srinath T. V. Setty
2. Dan Boneh
3. Michael Walfish
4. Andrew Justin Blumberg
5. Peter Kairouz
6. Eli Ben-Sasson
7. Eran Tromer
8. Adrià Gascón

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].”
• Geppetto: Versatile Verifiable Computation (2015, background): “Recently, several lines of work [9, 46, 49, 52] on verifiable computation [28] have combined theoretical and engineering innovations to build systems that can verify the results of generalpurpose outsourced computations while making at most cryptographic assumptions.”
• Pinocchio: Nearly Practical Verifiable Computation (2013, methodology): “Recall that GGPR show how to transform a regular QAP into a strong QAP, but the transformation more than triples the degree of the QAP.”
• Verifying computations with state (2013, background): “There is also a body of this work on this problem (starting from [19]) which relies on fully-homomorphic encryption (FHE) and ideas from secure multi-party protocols.”
• Securely Outsourcing Attribute-Based Encryption with Checkability (2014, background): “Another approach might be to leverage recent general outsourcing technique or delegating computation [21], [22], [23], [24], [25] based on fully homomorphic encryption or interactive proof system .”
• Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “that, unfortunately, our reductions cannot be used to benefit protocols that do not support nondeterminism; such protocols include all existing schemes for delegating polynomialtime functions, such as [46, 34, 25, 3, 21, 58].”
• Foundations of garbled circuits (2012, background): “5 for an example—consists of an Φ circ none NPS99 [46] privacy-preserving auctions prv Φ circ proxy OT KO04 [34] 2-party SFE (malicious) prv Φ circ OT, ZK proofs, commitment, trapdoor perm FAZ05 [19] private credit checking prv Φ size sym encryption FM06 [44] 2-party SFE (malicious) prv Φ circ OT, c”
• 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].”
• Quadratic Span Programs and Succinct NIZKs without PCPs (2013, methodology): “In the full version [22], we use our QSPbased SNARK to achieve a very efficient scheme for public verifiable computation [21, 39].”
• A Survey on Mobile Edge Computing: The Communication Perspective (2017, background): “computation tasks without the need of knowing the original user data and the correctness of the computation results can be verified, which can be realized by encryption algorithms and verifiable computing techniques [225].”
• Verifiable Delegation of Computation over Large Datasets (2011, background): “We prove our results in a stronger version of the [27] definition of verifiable computation scheme.”
• Secure Multiparty Sorting Protocols with Covert Privacy (2016, methodology): “Techniques of verifiable computation [15] may be used to turn passively secure SMC protocols into covertly secure protocols [25, 26].”
• Practical verified computation with streaming interactive proofs (2011, background): “A different line of work has used fully homomorphic encryption to ensure integrity, privacy, and reusability in delegated computation [18, 12, 11].”
• Functional Signatures and Pseudorandom Functions (2014, methodology): “We formalize these requirements below, following the definition introduced by Gennaro et al. in [GGP10].”
• Resolving the conflict between generality and plausibility in verified computation (2013, background): “Although there are many protocols for general-purpose verified computation in the literature [26, 30, 31, 33, 34] and have been for a long time [8], the theory, if implemented naively, is preposterously expensive: hundreds of trillions of CPU-years or more to verify simple computations [52].”
• Token-Based Cloud Computing Secure Outsourcing of Data and Arbitrary Computations with Lower Latency (2010, background): “Arbitrary computation on confidential data can be achieved with fully homomorphic encryption [12], in combination with garbled circuits [30] for verifiability [11].”