[Resource Topic] 2018/861: Delegating Computations with (almost) Minimal Time and Space Overhead

Welcome to the resource topic for 2018/861

Delegating Computations with (almost) Minimal Time and Space Overhead

Authors: Justin Holmgren, Ron D. Rothblum


The problem of verifiable delegation of computation considers a setting in which a client wishes to outsource an expensive computation to a powerful, but untrusted, server. Since the client does not trust the server, we would like the server to certify the correctness of the result. Delegation has emerged as a central problem in cryptography, with a flurry of recent activity in both theory and practice. In all of these works, the main bottleneck is the overhead incurred by the server, both in time and in space. Assuming (sub-exponential) LWE, we construct a one-round argument-system for proving the correctness of any time T and space S RAM computation, in which both the verifier and prover are highly efficient. The verifier runs in time n \cdot polylog(T) and space polylog(T), where n is the input length. Assuming S \geq \max(n,polylog(T)), the prover runs in time \tilde{O}(T) and space S + o(S), and in many natural cases even S+polylog(T). Our solution uses somewhat homomorphic encryption but, surprisingly, only requires homomorphic evaluation of arithmetic circuits having multiplicative depth (which is a main bottleneck in homomorphic encryption) \log_2\log(T)+O(1). Prior works based on standard assumptions had a T^c time prover, where c \geq 3 (at the very least). As for the space usage, we are unaware of any work, even based on non-standard assumptions, that has space usage S+polylog(T). Along the way to constructing our delegation scheme, we introduce several technical tools that we believe may be useful for future work.

ePrint: https://eprint.iacr.org/2018/861

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .