Paper 2018/1241

Universally Composable Accumulators

Foteini Baldimtsi, Ran Canetti, and Sophia Yakoubov

Abstract

Accumulators, first introduced by Benaloh and de Mare (Eurocrypt 1993), are compact representations of arbitrarily large sets and can be used to prove claims of membership or non-membership about the underlying set. They are almost exclusively used as building blocks in real-world complex systems, including anonymous credentials, group signatures and, more recently, anonymous cryptocurrencies. Having rigorous security analysis for such systems is crucial for their adoption and safe use in the real world, but it can turn out to be extremely challenging given their complexity. In this work, we provide the first universally composable (UC) treatment of cryptographic accumulators. There are many different types of accumulators: some support additions, some support deletions and some support both; and, orthogonally, some support proofs of membership, some support proofs of non-membership, and some support both. Additionally, some accumulators support public verifiability of set operations, and some do not. Our UC definition covers all of these types of accumulators concisely in a single functionality, and captures the two basic security properties of accumulators: correctness and soundness. We then prove the equivalence of our UC definition to standard accumulator definitions. This implies that existing popular accumulator schemes, such as the RSA accumulator, already meet our UC definition, and that the security proofs of existing systems that leverage such accumulators can be significantly simplified. Finally, we use our UC definition to get simple proofs of security. We build an accumulator in a modular way out of two weaker accumulators (in the style of Baldimtsi et. al (Euro S&P 2017), and we give a simple proof of its UC security. We also show how to simplify the proofs of security of complex systems such as anonymous credentials. Specifically, we show how to extend an anonymous credential system to support revocation by utilizing our results on UC accumulators.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. CT-RSA 2020
Keywords
universal composabilityaccumulators
Contact author(s)
sonka @ bu edu
History
2019-12-06: revised
2018-12-31: received
See all versions
Short URL
https://ia.cr/2018/1241
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/1241,
      author = {Foteini Baldimtsi and Ran Canetti and Sophia Yakoubov},
      title = {Universally Composable Accumulators},
      howpublished = {Cryptology ePrint Archive, Paper 2018/1241},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/1241}},
      url = {https://eprint.iacr.org/2018/1241}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.