Paper 2024/505
RSA-Based Dynamic Accumulator without Hashing into Primes
Abstract
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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- RSA AccumulatorCryptographic AccumulatorVDFWebPKI
- Contact author(s)
-
vyoudomk @ cs brown edu
anna @ cs brown edu - History
- 2024-04-15: revised
- 2024-03-29: received
- See all versions
- Short URL
- https://ia.cr/2024/505
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/505, 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}, url = {https://eprint.iacr.org/2024/505} }