Cryptology ePrint Archive: Report 2018/1241

Universally Composable Accumulators

Foteini Baldimtsi and 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. 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 using our UC definition.

Category / Keywords: foundations / universal composability, accumulators

Date: received 28 Dec 2018

Contact author: sonka at bu edu

Available format(s): PDF | BibTeX Citation

Version: 20181231:120929 (All versions of this report)

Short URL: ia.cr/2018/1241


[ Cryptology ePrint archive ]