Sublinear Zero-Knowledge Arguments for RAM Programs

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 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 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.