Paper 2017/129
Sublinear ZeroKnowledge Arguments for RAM Programs
Payman Mohassel, Mike Rosulek, and Alessandra Scafuro
Abstract
We describe a new succinct zeroknowledge argument protocol with the following properties. The prover commits to a large dataset $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 onetime initial commitment to $M$. Known sublinear zeroknowledge 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 blackbox way and is UCsecure in the {\em global}, nonprogrammable random oracle, hence it does not rely on any trusted setup assumption.
Metadata
 Available format(s)
 Publication info
 Published by the IACR in EUROCRYPT 2017
 Keywords
 zeroknowledgeoblivious ram
 Contact author(s)

payman mohassel @ gmail com
mikero @ gmail com
ascafur @ ncsu edu  History
 20170216: received
 Short URL
 https://ia.cr/2017/129
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/129, author = {Payman Mohassel and Mike Rosulek and Alessandra Scafuro}, title = {Sublinear ZeroKnowledge Arguments for RAM Programs}, howpublished = {Cryptology ePrint Archive, Paper 2017/129}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/129}}, url = {https://eprint.iacr.org/2017/129} }