Paper 2020/1239

Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation

Alin Tomescu, Yu Xia, and Zachary Newman


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.

Available format(s)
Public-key cryptography
Publication info
authenticated dictionariescommitmentsaccumulatorsRSAhidden-order groups
Contact author(s)
alint @ vmware com
2020-10-09: received
Short URL
Creative Commons Attribution


      author = {Alin Tomescu and Yu Xia and Zachary Newman},
      title = {Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1239},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.