International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 26 May 2015

Zhangxiang Hu, Payman Mohassel, Mike Rosulek
ePrint Report ePrint Report
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.

Expand

Additional news items may be found on the IACR news page.