Transparency logs via append-only authenticated dictionaries

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

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

29 Scopus citations

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

Original languageEnglish
Title of host publicationCCS 2019 - Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security
Pages1299-1316
Number of pages18
ISBN (Electronic)9781450367479
DOIs
StatePublished - 6 Nov 2019
Event26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019 - London, United Kingdom
Duration: 11 Nov 201915 Nov 2019

Publication series

NameProceedings of the ACM Conference on Computer and Communications Security
ISSN (Print)1543-7221

Conference

Conference26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019
Country/TerritoryUnited Kingdom
CityLondon
Period11/11/1915/11/19

Keywords

  • Append-only
  • Authenticated dictionaries
  • Bilinear accumulators
  • Merkle trees
  • Polynomials
  • RSA accumulators
  • Transparency logs

Fingerprint

Dive into the research topics of 'Transparency logs via append-only authenticated dictionaries'. Together they form a unique fingerprint.

Cite this