Bandwidth-efficient Transparency Logs via Append-only Authenticated Dictionaries

Alin Tomescu


Transparency logs enable anyone to audit a potentially malicious service, paving the way towards a more ac- countable Internet. For example, Certificate Transparency (CT) enables domain owners to audit Certificate Authorities (CAs) and detect impersonation. Yet to achieve their full potential, transparency logs must be easily auditable by everyone. 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 this paper, we formalize and instantiate a new primitive called an append-only authenticated dictionary (AAD) that addresses this gap. Our construction provides succinct proofs for both (non)membership and append-only checks, solving an open problem in the authenticated data structures literature. We believe AADs can help scale transparency logs and add more accountability to today?s Internet.


Alin is a PhD candidate at MIT focusing on public-key distribution for HTTPS and secure messaging. His interests lie at the intersection of theory and practice: he enjoys applied cryptography and building systems.Recently, Alin worked on Catena, a system that leverages the Bitcoin blockchain to prevent equivocation attacks on public-key directories. In the past, Alin has worked on privacy-preserving file systems, private social networking and secure email. Alin's other interests include cryptocurrencies, anonymous networks and distributed systems in general.

Time and Place

Tuesday, June 26, 4:15pm
Gates 463A