Cryptology ePrint Archive: Report 2020/1239

Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation

Alin Tomescu and Yu Xia and Zachary Newman

Abstract: Authenticated dictionaries (ADs) are a key building block of many cryptographic systems, such as transparency logs, distributed file systems and cryptocurrencies. In this paper, we propose a new notion of cross-incremental proof (dis)aggregation for authenticated dictionaries, which enables aggregating multiple proofs with respect to different dictionaries into a single, succinct proof. Importantly, this aggregation can be done incrementally and can be later reversed via disaggregation. We give an efficient authenticated dictionary construction from hidden-order groups that achieves cross-incremental (dis)aggregation. Our construction also supports updating digests, updating (cross-)aggregated proofs and precomputing all proofs efficiently. This makes it ideal for stateless validation in cryptocurrencies with smart contracts. As an additional contribution, we give a second authenticated dictionary construction, which can be used in more malicious settings where dictionary digests are adversarially-generated, but features only “one-hop” proof aggregation (with respect to the same digest). We add support for append-only proofs to this construction, which gives us an append-only authenticated dictionary (AAD) that can be used for transparency logs and, unlike previous AAD constructions, supports updating and aggregating proofs.

Category / Keywords: public-key cryptography / authenticated dictionaries, commitments, accumulators, RSA, hidden-order groups

Date: received 7 Oct 2020, last revised 7 Oct 2020

Contact author: alint at vmware com

Available format(s): PDF | BibTeX Citation

Version: 20201009:113351 (All versions of this report)

Short URL: ia.cr/2020/1239


[ Cryptology ePrint archive ]