Welcome to the resource topic for 2017/129
Title:
Sublinear Zero-Knowledge Arguments for RAM Programs
Authors: Payman Mohassel, Mike Rosulek, 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.
ePrint: https://eprint.iacr.org/2017/129
Talk: https://www.youtube.com/watch?v=BZl2q8EBV2o
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .