Cryptology ePrint Archive: Report 2015/497

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