**Sublinear Zero-Knowledge Arguments for RAM Programs**

*Payman Mohassel and 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.

**Category / Keywords: **zero-knowledge, oblivious ram

**Original Publication**** (in the same form): **IACR-EUROCRYPT-2017

**Date: **received 13 Feb 2017

**Contact author: **mikero at gmail com, payman mohassel@gmail com, ascafur@ncsu edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20170216:220242 (All versions of this report)

**Short URL: **ia.cr/2017/129

[ Cryptology ePrint archive ]