![Proofs, Consensus, and Decentralizing Society_hi-res logo](/sites/default/files/styles/workshop_banner_sm_1x/public/2023-01/Proofs%2C%20Consensus%2C%20and%20Decentralizing%20Society_hi-res.png.jpg?itok=gluZ2qCs)
Abstract
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).