On the Amortized Complexity of Zero-Knowledge Protocols
On the Amortized Complexity of Zero-Knowledge Protocols
复制标题
关于零知识协议的摊销复杂性
DOI：
10.1007/s00145-013-9145-x
复制
发表时间：
2013
影响因子：
3
通讯作者：
Cramer R
中科院分区：
文献类型：
--
作者：
Cramer R
我们提出了一种通用的技术，可以提高一大类问题的零知识协议的复杂性，其中以前最知名的解决方案是一个简单的切割和选择风格的协议，即，其中，问题实例x和错误概率2−nwasO（|X| n）比特。通过使用我们的技术来同时证明实例，我们可以将每个实例的证明大小降低到O（|X| +n）比特，同时不使用计算假设。我们的技术适用的例子包括证明二次残差，证明子群成员资格和知识的离散矩阵在群体中的未知顺序，后者的区间证明，以及证明明文知识的各种类型的同态加密方案。首先，我们提出我们的协议，作为验证协议，并将其扩展到零知识证明的知识。
We propose a general technique that allows improving the complexity of zero-knowledge protocols for a large class of problems where previously the best known solution was a simple cut-and-choose style protocol, i.e., where the size of a proof for problem instancexand error probability 2−nwasO(|x|n) bits. By using our technique to proveninstances simultaneously, we can bring down the proof size per instance toO(|x|+n) bits for the same error probability while using no computational assumptions. Examples where our technique applies include proofs for quadratic residuosity, proofs of subgroup membership and knowledge of discrete logarithms in groups of unknown order, interval proofs of the latter, and proofs of plaintext knowledge for various types of homomorphic encryption schemes. We first propose our protocols asΣ-protocols and extend them later to zero-knowledge proofs of knowledge.
任意阿贝尔群上的最优黑盒秘密共享
DOI：
10.1007/3-540-45708-9_18
发表时间：
2002
期刊：
Proceedings of IEEE 36th Annual Foundations of Computer Science
影响因子：
--
作者：
R. Cramer;S. Fehr
通讯作者：
S. Fehr
DOI：
10.1145/129712.129780
发表时间：
1992-07
期刊：
--
影响因子：
--
作者：
M. Franklin;M. Yung
通讯作者：
M. Franklin;M. Yung