Delegating Computations with (almost) Minimal Time and Space Overhead

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. Assuming S >= max(n * polylog(T)), the prover runs in time 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).