Justin Holmgren (Princeton University)
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).