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 w:Ri(M,w)=1, where Ri 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 Ri (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 and are therefore sublinear only in an amortized sense, or require that the computational cost for the prover is proportional to 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in EUROCRYPT 2017
Keywords
zero-knowledgeoblivious ram
Contact author(s)
payman mohassel @ gmail com
mikero @ gmail com
ascafur @ ncsu edu
History
2017-02-16: received
Short URL
https://ia.cr/2017/129
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/129,
      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},
      url = {https://eprint.iacr.org/2017/129}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.