Efficient zero-knowledge proofs of non-algebraic statements with sublinear amortized cost
Advances in Cryptology--CRYPTO 2015: 35th Annual Cryptology Conference, Santa …, 2015•Springer
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 ∃ w: R (M, x, w)= 1∃ 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 random-access machine
(RAM) implementation of R, up to polylogarithmic factors. In particular, the cost per proof in …
can repeatedly prove NP relations about that dataset. That is, for any (public) relation R and
x, the prover can prove that ∃ w: R (M, x, w)= 1∃ 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 random-access machine
(RAM) implementation of R, up to polylogarithmic factors. In particular, the cost per proof in …
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 . 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 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.
Springer