Paper 2018/721

Transparency Logs via Append-only Authenticated Dictionaries

Alin Tomescu, Vivek Bhupatiraju, Dimitrios Papadopoulos, Charalampos Papamanthou, Nikos Triandopoulos, and Srinivas Devadas


Transparency logs allow users to audit a potentially malicious service, paving the way towards a more accountable Internet. For example, Certificate Transparency (CT) enables domain owners to audit Certificate Authorities (CAs) and detect impersonation attacks. Yet, to achieve their full potential, transparency logs must be bandwidth-efficient when queried by users. Specifically, everyone should be able to efficiently look up log entries by their key and efficiently verify that the log remains append-only. Unfortunately, without additional trust assumptions, current transparency logs cannot provide both small-sized lookup proofs and small-sized append-only proofs. In fact, one of the proofs always requires bandwidth linear in the size of the log, making it expensive for everyone to query the log. In this paper, we address this gap with a new primitive called an append-only authenticated dictionary (AAD). Our construction is the first to achieve (poly)logarithmic size for both proof types and helps reduce bandwidth consumption in transparency logs. This comes at the cost of increased append times and high memory usage, both of which remain to be improved to make practical deployment possible.

Note: Fixed several typos, including an unfortunate one in the AAD definition. Future small updates to the paper can be found on GitHub at

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. ACM CCS 2019
implementationkey managementpublic-key cryptography
Contact author(s)
alinush @ mit edu
2020-12-15: last of 2 revisions
2018-08-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alin Tomescu and Vivek Bhupatiraju and Dimitrios Papadopoulos and Charalampos Papamanthou and Nikos Triandopoulos and Srinivas Devadas},
      title = {Transparency Logs via Append-only Authenticated Dictionaries},
      howpublished = {Cryptology ePrint Archive, Paper 2018/721},
      year = {2018},
      doi = {10.1145/3319535.3345652},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.