Universal Accumulators with Efficient Nonmembership Proofs
Universal Accumulators with Efficient Nonmembership Proofs
复制标题
DOI：
10.1007/978-3-540-72738-5_17
复制
发表时间：
2007-06
期刊：
影响因子：
--
通讯作者：
Jiangtao Li;Ninghui Li;Rui Xue
中科院分区：
文献类型：
--
作者：
Jiangtao Li;Ninghui Li;Rui Xue
基于累加器的概念，我们提出了一种新的密码方案--通用累加器。该方案使人们能够使用短累加器提交一组值，并有效地计算已经累积的任何值的成员资格见证。与传统的累加器不同，该方案还可以有效地计算尚未累加的任意值的非成员见证。给出了一种通用累加器的构造，并基于强RSA假设证明了它的安全性。我们进一步提出了一种动态万能累加器的结构，这种结构允许以恒定的计算代价动态地添加和删除输入。我们的结构直接建立在Camenisch和Lysyanskaya的动态累加器方案上。通用累加器可以被视为支持非成员见证的动态累加器的扩展。我们还给出了一个有效的零知识证明协议，用于证明承诺值不在累加器中。我们的动态通用累加器结构支持以匿名方式高效地撤销成员资格。
Based on the notion of accumulators, we propose a new cryptographic scheme called universal accumulators. This scheme enables one to commit to a set of values using a short accumulator and to efficiently compute a membership witness of any value that has been accumulated. Unlike traditional accumulators, this scheme also enables one to efficiently compute a nonmembership witness of any value that has not been accumulated. We give a construction for universal accumulators and prove its security based on the strong RSA assumption. We further present a construction for dynamic universal accumulators; this construction allows one to dynamically add and delete inputs with constant computational cost. Our construction directly builds upon Camenisch and Lysyanskaya’s dynamic accumulator scheme. Universal accumulators can be seen as an extension to dynamic accumulators with support of nonmembership witness. We also give an efficient zero-knowledge proof protocol for proving that a committed value is not in the accumulator. Our dynamic universal accumulator construction enables efficient membership revocation in an anonymous fashion.