Paper 2021/638

Efficient Constructions of Pairing Based Accumulators

Ioanna Karantaidou and Foteini Baldimtsi


Cryptographic accumulators are a crucial building block for a variety of applications where you need to represent a set of elements in a compact format while still being able to provide proofs of (non)membership. In this work, we give a number of accumulator constructions for the bilinear pairing setting in the trapdoor-based scenario, where a trusted manager maintains the accumulator. Using modular accumulator techniques, we first present the first optimally efficient (in terms of communication cost) dynamic, positive accumulators in the pairing setting. Additionally, we present a novel modular approach to construct universal accumulators that avoid costly non-membership proofs. We instantiate our generic construction and present the first universal accumulator in the bilinear pairing setting, that achieves constant parameter size, constant cost for element additions/deletions and witness generation by the manager, constant witness updates by the users and constant (non)membership verification. We finally show how our proposed universal accumulator construction can give rise to efficient ZK accumulators with constant non-membership witness updates.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision.CSF 2021
accumulatorsbilinear pairingsmodular constructions
Contact author(s)
ikaranta @ gmu edu
foteini @ gmu edu
2021-05-17: received
Short URL
Creative Commons Attribution


      author = {Ioanna Karantaidou and Foteini Baldimtsi},
      title = {Efficient Constructions of Pairing Based Accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2021/638},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.