TY - GEN
T1 - Transparency logs via append-only authenticated dictionaries
AU - Tomescu, Alin
AU - Papamanthou, Charalampos
AU - Bhupatiraju, Vivek
AU - Triandopoulos, Nikos
AU - Papadopoulos, Dimitrios
AU - Devadas, Srinivas
N1 - Publisher Copyright:
© 2019 Copyright held by the owner/author(s). Publication rights licensed to ACM.
PY - 2019/11/6
Y1 - 2019/11/6
N2 - 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.
AB - 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.
KW - Append-only
KW - Authenticated dictionaries
KW - Bilinear accumulators
KW - Merkle trees
KW - Polynomials
KW - RSA accumulators
KW - Transparency logs
UR - http://www.scopus.com/inward/record.url?scp=85075939571&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85075939571&partnerID=8YFLogxK
U2 - 10.1145/3319535.3345652
DO - 10.1145/3319535.3345652
M3 - Conference contribution
AN - SCOPUS:85075939571
T3 - Proceedings of the ACM Conference on Computer and Communications Security
SP - 1299
EP - 1316
BT - CCS 2019 - Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security
T2 - 26th ACM SIGSAC Conference on Computer and Communications Security, CCS 2019
Y2 - 11 November 2019 through 15 November 2019
ER -