Paper 2020/1239

Authenticated Dictionaries with Cross-Incremental Proof (Dis)aggregation

Alin Tomescu, 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
authenticated dictionariescommitmentsaccumulatorsRSAhidden-order groups
Contact author(s)
alint @ vmware com
History
2020-10-09: received
Short URL
https://ia.cr/2020/1239
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1239,
      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{https://eprint.iacr.org/2020/1239}},
      url = {https://eprint.iacr.org/2020/1239}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.