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

*Zhangxiang Hu and Payman Mohassel and 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.

**Category / Keywords: **cryptographic protocols / zero-knowledge, secure computation, oblivious ram, garbled circuits

**Original Publication**** (in the same form): **IACR-CRYPTO-2015

**Date: **received 25 May 2015, last revised 26 May 2015

**Contact author: **rosulekm at eecs oregonstate edu

**Available format(s): **PDF | BibTeX Citation

**Version: **20150526:152321 (All versions of this report)

**Short URL: **ia.cr/2015/497

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]