SoK: Cryptographic Authenticated Dictionaries
Harjasleen Malvai
Network and Distributed System Security (NDSS) Symposium 2026 · Day 3 · Applied Cryptography
**Cryptographic authenticated dictionaries** are data structures that provide not just key-value storage but also **proofs** about the correctness of lookup results -- proofs that a returned value is genuinely associated with a given key at a specific point in time. These structures underpin critical security infrastructure including **key transparency** (Meta/WhatsApp, Apple iMessage), **binary transparency** (verifying software releases), **revocation transparency** (TLS certificate validation), **blockchain state management**, and **news transparency**. This Systematization of Knowledge (SoK) paper surveys **30 schemes spanning 30 years** of literature, providing a unified framework of five trust models, a map of three core security definitions, a taxonomy of constructions, and an asymptotic performance survey that reveals an intriguing open question: no known construction achieves both **constant-time lookup** and **logarithmic-time update** simultaneously.
AI review
A comprehensive survey of cryptographic authenticated dictionaries spanning 30 years and 30 constructions. Useful reference for cryptographic infrastructure builders but contains no offensive security content, no vulnerabilities, and no novel attacks or defenses.