Cryptology ePrint Archive: Report 2015/718

Efficient Asynchronous Accumulators for Distributed PKI

Leonid Reyzin and Sophia Yakoubov

Abstract: Cryptographic accumulators are a tool for compact set representation and secure set membership proofs. When an element is added to a set by means of an accumulator, a membership witness is generated. This witness can later be used to prove the membership of the element. Typically, the membership witness has to be synchronized with the accumulator value, and to be updated every time another element is added to the accumulator. In this work we propose an accumulator that, unlike any prior scheme, does not require strict synchronization.

In our construction a membership witness needs to be updated only a logarithmic number times in the number of subsequent element additions. Thus, an out-of-date witness can be easily made current. Vice versa, a verifier with an out-of-date accumulator value can still verify a current membership witness. These properties make our accumulator construction uniquely suited for use in distributed applications, such as blockchain-based public key infrastructures.

Category / Keywords: cryptographic protocols / cryptographic accumulators, PKI

Date: received 18 Jul 2015

Contact author: sonka at bu edu

Available format(s): PDF | BibTeX Citation

Version: 20150720:065903 (All versions of this report)

Short URL: ia.cr/2015/718

Discussion forum: Show discussion | Start new discussion