Cryptology ePrint Archive: Report 2018/721

Transparency Logs via Append-only Authenticated Dictionaries

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

Abstract: 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, trans- parency logs must be efficiently auditable. Specifically, everyone should be able to verify both (non)membership of log entries and that the log remains append-only. Unfortunately, current transparency logs either provide small-sized (non)membership proofs or small-sized append-only proofs, but never both. In fact, one of the proofs always requires bandwidth linear in the size of the log, making it expensive for everyone to audit the log and resulting in a few “opaque” trusted auditors. 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. Moreover, our experimental evaluation is very encouraging: for reasonable application scenarios, our AAD reduces the total communication bandwidth in transparency schemes by more than 200x, compared to previous approaches.

Category / Keywords: cryptographic protocols / implementation; key management; public-key cryptography

Date: received 1 Aug 2018

Contact author: alinush at mit edu

Available format(s): PDF | BibTeX Citation

Version: 20180803:125704 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]