Improved Delegation of Computation using Fully Homomorphic Encryption

By Kai-Min Chung, Yael Tauman Kalai, Salil P. Vadhan. 2010

410 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

Pinocchio: Nearly Practical Verifiable Computation (2013, background): “Several previous VC schemes [22, 23] were not public, but rather designated verifier, meaning that the verification key V KF must be kept secret.”
How to Delegate and Verify in Public: Verifiable Computation from Attribute-based Encryption (2012, methodology): “In some of the protocols [1] [3] [9] [11], a client who wishes to delegate computation of a function F is required to first run an expensive pre-processing phase (wherein her computation is linear in the size of the circuit for F) to generate a (small) secret key SK F and a (large) evaluation key…”
Verifying Computations with Streaming Interactive Proofs (2011, background): “Figure 1 shows a small example on the vector a = [ 2 , 3 , 8 , 1 , 7 , 6 , 4 , 3 ] .”
A Survey of Verifiable Computation (2017, background): “Although this scheme did not totally satisfy the notion of FHE due to its limits on circuit depth, it indeed inspires lots of researchers to make efforts on improving the efficiency of SHE [3 – 9].”
Attribute-based encryption for circuits (2013, background): “A verifiable delegation scheme allows a computationally weak client to delegate expensive computations to the cloud with the assurance that a malicious cloud cannot convince the client to accept an incorrect computation [Micali 2000; Goldwasser et al. 2008; Gennaro et al. 2010; Chung et al. 2010; Ap”
Resolving the conflict between generality and plausibility in verified computation (2013, background): “For example, several protocols [20, 26] employ fully homomorphic encryption (FHE) [28] in protocols for non-interactive verifiable computation.”
Practical delegation of computation using multiple servers (2011, methodology): “In particular, all known protocols rely either on arithmetization and PCP techniques [20, 12], or provide only amortized performance advantages and rely on fully homomorphic encryption [11, 9].”
Securing Fog Computing for Internet of Things Applications: Challenges and Solutions (2018, methodology): “[189] utilized full homomorphic encryption schemes to construct a”
Attribute-Based Encryption With Verifiable Outsourced Decryption (2013, background): “these schemes [19], [20], [23], [24] focus on delegating general functions, and are not sufficiently efficient for the problem at hand.”
Foundations of garbled circuits (2012, background): “(However, as we have noted before, non-trivial secure outsourcing may be achieved by entirely different means [30].”
Homomorphic Signatures for Polynomial Functions (2011, background): “In [16, 13, 4] and in [22] (in the non-interactive setting) the interaction between the server and the client is tailored to the client and the client uses a secret key to verify the results.”
Making argument systems for outsourced computation practical (sometimes) (2012, background): “scheme [37] has led to new protocols for verifiable noninteractive computation [28, 36] with input hiding.”
Verifying computations without reexecuting them (2015, background): “…this primitive to apply simple PCP constructions to verifying general-purpose outsourced computations; and a couple of years later, Gentry’s breakthrough protocol for fully homomorphic encryption (FHE) [23] led to work (GGP) on non-interactive protocols for general-purpose computations [17, 21].”