Paper 2017/129

Sublinear Zero-Knowledge Arguments for RAM Programs

Payman Mohassel, Mike Rosulek, and Alessandra Scafuro


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.

Available format(s)
Publication info
Published by the IACR in EUROCRYPT 2017
zero-knowledgeoblivious ram
Contact author(s)
payman mohassel @ gmail com
mikero @ gmail com
ascafur @ ncsu edu
2017-02-16: received
Short URL
Creative Commons Attribution


      author = {Payman Mohassel and Mike Rosulek and Alessandra Scafuro},
      title = {Sublinear Zero-Knowledge Arguments for RAM Programs},
      howpublished = {Cryptology ePrint Archive, Paper 2017/129},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.