Paper 2026/1276 Original: eprint.iacr.org/2026/1276 ↗
Forget-me-not Trees: Mass-scale Auditable Key Transparency from Hash Functions
Abstract
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.
- History
- 2026-06-21: last updated
- 2026-06-17: published
- Short URL
- https://ia.cr/2026/1276
- License
- https://creativecommons.org/licenses/by/4.0/
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}
}