Universal Accumulators with Efficient Nonmembership Proofs Export

@incollection{citeulike:2240632, abstract = {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.}, author = {Li, Jiangtao and Li, Ninghui and Xue, Rui}, citeulike-article-id = {2240632}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/978-3-540-72738-5_17}, doi = {10.1007/978-3-540-72738-5_17}, journal = {Applied Cryptography and Network Security}, keywords = {accumulators, membership}, pages = {253--269}, posted-at = {2008-01-16 19:39:49}, priority = {2}, title = {Universal Accumulators with Efficient Nonmembership Proofs}, url = {http://dx.doi.org/10.1007/978-3-540-72738-5_17}, year = {2007} }

TY - CHAP ID - citeulike:2240632 L3 - citeulike-article-id:2240632 N2 - 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. JF - Applied Cryptography and Network Security EP - 269 TI - Universal Accumulators with Efficient Nonmembership Proofs SP - 253 KW - accumulators KW - membership AU - Li, Jiangtao AU - Li, Ninghui AU - Xue, Rui PY - 2007/// UR - http://dx.doi.org/10.1007/978-3-540-72738-5_17 ER -