Paper 2026/1276
Forget-me-not Trees: Mass-scale Auditable Key Transparency from Hash Functions
, University of Maryland, College ParkAbstract
Modern, deployed key transparency systems rely on auditors to ensure that updates to the set of keys are well-structured, allowing clients to efficiently monitor their own keys. In practice, the server's consistency proofs are very large, requiring computationally powerful auditors; as a result, real-world deployments have very few auditors. We propose a new key transparency system based on a new data structure called Forget-me-not trees, which is a careful composition of Merkle trees and Bloom filters. The resulting system reduces the size of audit proofs by $\approx500\times$, from 15MB-30MB down to only 30KB-60KB. Our construction is the first mass-scale auditable key transparency system that relies only on hash functions.
Metadata
- Available format(s)
-
PDF
- Category
- Applications
- Publication info
- Preprint.
- Keywords
- Key Transparency
- Contact author(s)
- kaptchuk @ umd edu
- History
- 2026-06-21: revised
- 2026-06-17: received
- See all versions
- Short URL
- https://ia.cr/2026/1276
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1276,
author = {Gabriel Kaptchuk},
title = {Forget-me-not Trees: Mass-scale Auditable Key Transparency from Hash Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1276},
year = {2026},
url = {https://eprint.iacr.org/2026/1276}
}
