Paper 2017/129

Sublinear Zero-Knowledge Arguments for RAM Programs

Payman Mohassel, Mike Rosulek, and Alessandra Scafuro

Abstract

We describe a new succinct zero-knowledge argument protocol with the following properties. The prover commits to a large data-set $M$, and can thereafter prove many statements of the form $\exists w : \mathcal{R}_i(M,w)=1$, where $\mathcal{R}_i$ is a public function. The protocol is {\em succinct} in the sense that the cost for the verifier (in computation \& communication) does not depend on $|M|$, not even in any initialization phase. In each proof, the computation/communication cost for {\em both} the prover and the verifier is proportional only to the running time of an oblivious RAM program implementing $\mathcal{R}_i$ (in particular, this can be sublinear in $|M|$). The only costs that scale with $|M|$ are the computational costs of the prover in a one-time initial commitment to $M$. Known sublinear zero-knowledge proofs either require an initialization phase where the work of the verifier is proportional to $|M|$ and are therefore sublinear only in an amortized sense, or require that the computational cost for the prover is proportional to $|M|$ upon {\em each proof}. Our protocol uses efficient crypto primitives in a black-box way and is UC-secure in the {\em global}, non-programmable random oracle, hence it does not rely on any trusted setup assumption.