### Merkle^2: A Low-Latency Transparency Log System

Yuncong Hu, Kian Hooshmand, Harika Kalidhindi, Seung Jin Yang, and Raluca Ada Popa

##### Abstract

Transparency logs are designed to help users audit untrusted servers. For example, Certificate Transparency (CT) enables users to detect when a compromised Certificate Authority (CA) has issued a fake certificate. Practical state-of-the-art transparency log systems, however, suffer from high monitoring costs when used for low-latency applications. To reduce monitoring costs, such systems often require users to wait an hour or more for their updates to take effect, inhibiting low-latency applications. We propose $\text{Merkle}^2$, a transparency log system that supports both efficient monitoring and low-latency updates. To achieve this goal, we construct a new multi-dimensional, authenticated data structure that nests two types of Merkle trees, hence the name of our system, $\text{Merkle}^2$. Using this data structure, we then design a transparency log system with efficient monitoring and lookup protocols that enables low-latency updates. In particular, all the operations in $\text{Merkle}^2$ are independent of update intervals and are (poly)logarithmic to the number of entries in the log. $\text{Merkle}^2$ not only has excellent asymptotics when compared to prior work, but is also efficient in practice. Our evaluation shows that $\text{Merkle}^2$ propagates updates in as little as 1 second and can support 100× more users than state-of-the-art transparency logs.

Available format(s)
Category
Cryptographic protocols
Publication info
Published elsewhere. MINOR revision.IEEE S&P 2021
Keywords
key managementtransparency logmerkle treeauthenticated data structure
Contact author(s)
yuncong_hu @ berkeley edu
History
2021-05-31: revised
See all versions
Short URL
https://ia.cr/2021/453

CC BY

BibTeX

@misc{cryptoeprint:2021/453,
author = {Yuncong Hu and Kian Hooshmand and Harika Kalidhindi and Seung Jin Yang and Raluca Ada Popa},
title = {Merkle^2: A Low-Latency Transparency Log System},
howpublished = {Cryptology ePrint Archive, Paper 2021/453},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/453}},
url = {https://eprint.iacr.org/2021/453}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.