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

Publication
Aug 16, 2015
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  there 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.

  • Advances in Cryptology--CRYPTO 2015
  • Conference/Workshop Paper

BibTeX