Jingtao Li, Ninghui Li, and Rui Xue

CERIAS TR 2007-47

inproceedings

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

PDF

2007

Proceedings of 5th Conference on Applied Cryptography and Network Security (ACNS)

Li

In Proceedings of 5th Conference on Applied Cryptography and Network Security (ACNS), Zhuhai, China, June 2007

Applied Cryptograpy and Network Security

Most of this work was done while Jiangtao Li and Rui Xue were at Purdue University. This work is supported by NSF IIS-0430274, NSF CCR-0325951, and sponsors of CERIAS. Rui Xue is also supported by the Fund of the China Scholarship Council and the NSFC Grant 60373048. We thank the anonymous reviewers for their helpful comments.

2007-01-01

1. Introduction 2. Notations and Assumptions 3. Universal Accumulators 4. Dynamic Universal Accumulators 5. Efficient Proof That a Committed Value Was Not Accumulated 6. Application to Certificate and Membership Revocation 7. Conclusion

Universal Accumulators, Efficient Nonmembership Proofs

English

Cryptography