Paper 2020/777

Dynamic Universal Accumulator with Batch Update over Bilinear Groups

Giuseppe Vitto and Alex Biryukov


We propose a Dynamic Universal Accumulator in the Accumulator Manager setting for bilinear groups which extends Nguyen's positive accumulator and Au et al. and Damgård and Triandopoulos non-membership proof mechanism. The new features include support for batch addition and deletion operations as well as a privacy-friendly decentralized batch witness update protocol, where the witness update information is the same for all users. Together with a non-interactive zero-knowledge protocol, these make the proposed scheme suitable as an efficient and scalable Anonymous Credential System, accessible even by low-resource users. We show security of the proposed protocol in the Generic Group Model under a (new) generalized version of the t-SDH assumption and we demonstrate its practical relevance by providing and discussing an implementation realized using state-of-the-art libraries.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
accumulatoruniversaldynamicbatch updateprivacy-preserving KYCanonymous credentials
Contact author(s)
giuseppe vitto @ uni lu
alex biryukov @ uni lu
2021-09-13: last of 3 revisions
2020-06-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Giuseppe Vitto and Alex Biryukov},
      title = {Dynamic Universal Accumulator with Batch Update over Bilinear Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2020/777},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.