Delegating Computations with (Almost) Minimal Time and Space Overhead

Abstract

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 ⋅ polylog(T) and space polylog(T), where n is the input length. The prover runs in time quasilinear in T, in space S + o(S), and in some cases even space S + polylog(T). Our solution uses somewhat homomorphic encryption but, surprisingly, only requires homomorphic evaluation of arithmetic circuits having multiplicative depth (which is the main efficiency bottleneck in such schemes) that is lg(lg T)+O(1). Prior works based on standard assumptions had a poly(T) time prover, with an exponent of 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 hope will be useful for future work.