Paper 2024/505

RSA-Based Dynamic Accumulator without Hashing into Primes

Victor Youdom Kemmoe, Brown University
Anna Lysyanskaya, Brown University

A cryptographic accumulator is a compact data structure for representing a set of elements coming from some domain. It allows for a compact proof of membership and, in the case of a universal accumulator, non-membership of an element x in the data structure. A dynamic accumulator, furthermore, allows elements to be added to and deleted from the accumulator. Previously known RSA-based dynamic accumulators were too slow in practice because they required that an element in the domain be represented as a prime number. Accumulators based on settings other than RSA had other drawbacks such as requiring a prohibitively large common reference string or a trapdoor, or not permitting deletions. In this paper, we construct RSA-based dynamic universal accumulators that do not require that the accumulated elements be represented as primes. We also show how to aggregate membership and non-membership witnesses and batch additions and deletions. We demonstrate that the efficiency gains compared to previously known RSA-based accumulators are substantial, and, for the first time, make cryptographic accumulators a viable candidate for a certificate revocation mechanism as part of a WebPKI-type system.

Available format(s)
Public-key cryptography
Publication info
RSA AccumulatorCryptographic AccumulatorVDFWebPKI
Contact author(s)
vyoudomk @ cs brown edu
anna @ cs brown edu
2024-04-15: revised
2024-03-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Victor Youdom Kemmoe and Anna Lysyanskaya},
      title = {RSA-Based Dynamic Accumulator without Hashing into Primes},
      howpublished = {Cryptology ePrint Archive, Paper 2024/505},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.