Abstract
We introduce the notion of a dynamic accumulator. An accumulator scheme allows one to hash a large set of inputs into one short value, such that there is a short proof that a given input was incorporated into this value. A dynamic accumulator allows one to dynamically add and delete a value, such that the cost of an add or delete is independent of the number of accumulated values. We provide a construction of a dynamic accumulator and an efficient zero-knowledge proof of knowledge of an accumulated value. We prove their security under the strong RSA assumption. We then show that our construction of dynamic accumulators enables efficient revocation of anonymous credentials, and membership revocation for recent group signature and identity escrow schemes.
Chapter PDF
Similar content being viewed by others
Keywords
References
G. Ateniese, J. Camenisch, M. Joye, and G. Tsudik. A practical and provably secure coalition-resistant group signature scheme. In Advances in Cryptology — CRYPTO 2000, vol. 1880 of LNCS, pp. 255–270. Springer Verlag, 2000.
G. Ateniese and G. Tsudik. Quasi-efficient revocation of group signatures. http://www.eprint.iacr.org/2001/101, 2001.
N. Barić and B. Pfitzmann. Collision-free accumulators and fail-stop signature schemes without trees. In EUROCRYPT’ 97, vol. 1233 of LNCS, pp. 480–494.
J. Benaloh and M. de Mare. One-way accumulators: A decentralized alternative to digital signatures. In EUROCRYPT’ 93, vol. 765 of LNCS, pp. 274–285.
S. Brands. Rethinking Public Key Infrastructure and Digital Certificates — Building in Privacy. PhD thesis, Eindhoven Institute of Technology, Eindhoven, The Netherlands, 1999.
E. Bresson and J. Stern. Group signatures with efficient revocation. In Proceedings of PKC2001, vol. 1992 of LNCS, pp. 190–206. Springer, 2001.
J. Camenisch. Efficient and generalized group signatures. In Advances in Cryptology — EUROCRYPT’ 97, vol. 1233 of LNCS, pp. 465–479.
J. Camenisch and A. Lysyanskaya. Dynamic accumulators and application to efficient revocation of anonymous credentials. http://www.eprint.iacr.org/2001, 2001.
J. Camenisch and A. Lysyanskaya. Efficient non-transferable anonymous multi-show credential system with optional anonymity revocation. In Advances in Cryptology — EUROCRYPT 2001, vol. 2045 of LNCS, pp. 93–118.
J. Camenisch and A. Lysyanskaya. An identity escrow scheme with appointed verifiers. In CRYPTO 2001, vol. 2139 of LNCS, pp. 388–407.
J. Camenisch and M. Michels. A group signature scheme with improved efficiency. In Advances in Cryptology — ASIACRYPT’ 98, vol. 1514 of LNCS, pp. 160–174.
J. Camenisch and M. Michels. Separability and efficiency for generic group signature schemes. In CRYPTO’ 99, vol. 1666 of LNCS, pp. 413–430.
J. Camenisch and M. Stadler. Efficient group signature schemes for large groups. In Advances in Cryptology — CRYPTO’ 97, vol. 1296 of LNCS, pp. 410–424, 1997.
R. Canetti. Security and composition of multi-party cryptographic protocols. Journal of Cryptology, 13(1):143–202, 2000.
L. Chen and T. P. Pedersen. New group signature schemes. In Advances in Cryptology — EUROCRYPT’ 94, vol. 950 of LNCS, pp. 171–181, 1995.
R. Cramer and V. Shoup. A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In Advances in Cryptology — CRYPTO’ 98, vol. 1642 of LNCS, pp. 13–25, Berlin, 1998. Springer Verlag.
I. Damgøard and E. Fujisaki. An integer commitment scheme based on groups with hidden order. http://www.eprint.iacr.org/2001/064, 2001.
E. Fujisaki and T. Okamoto. Statistical zero knowledge protocols to prove modular polynomial relations. In CRYPTO’ 97, vol. 1294 of LNCS, pp. 16–30.
R. Gennaro, S. Halevi, and T. Rabin. Secure hash-and-sign signatures without the random oracle. In EUROCRYPT’ 99, vol. 1592 of LNCS, pp. 123–139.
O. Goldreich, S. Micali, and A. Wigderson. How to prove all NP statements in zero-knowledge and a methodology of cryptographic protocol design. In Advances in Cryptology — CRYPTO’ 86, vol. 263 of LNCS, pp. 171–185, 1987.
J. Kilian and E. Petrank. Identity escrow. In Advances in Cryptology — CRYPTO’ 98, vol. 1642 of LNCS, pp. 169–185, Berlin, 1998. Springer Verlag.
H.-J. Kim, J. I. Lim, and D. H. Lee. Efficient and secure member deletion in group signature schemes. In ICISC 2000, number 2015 in LNCS, pp. 150–161, 2001.
A. Lysyanskaya, R. Rivest, A. Sahai, and S. Wolf. Pseudonym systems. In Selected Areas in Cryptography, vol. 1758 of LNCS. Springer Verlag, 1999.
B. Pfitzmann and M. Waidner. Composition and integrity preservation of secure reactive systems. In Proc. 7th ACM CCS, pp. 245–254. ACM press, nov 2000.
T. Sander, A. Ta-Shma, and M. Yung. Blind, auditable membership proofs. In Financial Cryptography’ 00, vol. 1962 of LNCS, pp. 53–71, 2000.
A. Shamir. On the generation of cryptographically strong pseudorandom sequences. In ACM Transaction on Computer Systems, vol.1, pp. 38–44, 1983.
D. X. Song. Practical forward secure group signature schemes. In Proc. 8th ACM CCS, pp. 225–234. ACM press, nov 2001.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2002 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Camenisch, J., Lysyanskaya, A. (2002). Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials. In: Yung, M. (eds) Advances in Cryptology — CRYPTO 2002. CRYPTO 2002. Lecture Notes in Computer Science, vol 2442. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45708-9_5
Download citation
DOI: https://doi.org/10.1007/3-540-45708-9_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-44050-5
Online ISBN: 978-3-540-45708-4
eBook Packages: Springer Book Archive