Welcome to the resource topic for
**2015/497**

**Title:**

Efficient Zero-Knowledge Proofs of Non-Algebraic Statements with Sublinear Amortized Cost

**Authors:**
Zhangxiang Hu, Payman Mohassel, Mike Rosulek

**Abstract:**

We describe a zero-knowledge proof system in which a prover holds a large dataset M and can repeatedly prove NP relations about that dataset. That is, for any (public) relation R and x, the prover can prove that \exists w: R(M,x,w)=1. After an initial setup phase (which depends only on M), each proof requires only a constant number of rounds and has communication/computation cost proportional to that of a {\em random-access machine (RAM)} implementation of R, up to polylogarithmic factors. In particular, the cost per proof in many applications is sublinear in |M|. Additionally, the storage requirement between proofs for the verifier is constant.

**ePrint:**
https://eprint.iacr.org/2015/497

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 .