Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost
Efficient Zero-Knowledge Proofs of Non-algebraic Statements with Sublinear Amortized Cost
复制标题
具有次线性摊余成本的非代数语句的高效零知识证明
DOI：
10.1007/978-3-662-48000-7_8
复制
发表时间：
2015
影响因子：
19
通讯作者：
Mike Rosulek
中科院分区：
文献类型：
--
作者：
Zhangxiang Hu;Payman Mohassel;Mike Rosulek
我们描述了一个零知识证明系统，其中证明者拥有一个大数据集 M，并且可以重复证明关于该数据集的 NP 关系。也就是说，对于任何（公共）关系 R 和 x，证明者可以证明 \(\存在 w: R(M,x,w)=1\)。在初始设置阶段（仅取决于 M）之后，每个证明仅需要恒定的轮数，并且通信/计算成本与 R 的随机访问机 (RAM) 实现成正比，最高可达多对数因子。特别是，在许多应用中每个证明的成本在 |M| 中是次线性的。此外，验证者的证明之间的存储要求是恒定的。
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 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.