SoK: Cryptographic Authenticated Dictionaries

SoK: Cryptographic Authenticated Dictionaries

Speakers: Harjasleen Malvai

Conference: NDSS Symposium 2026

YouTube: https://www.youtube.com/watch?v=9BBK2lD0qD8

Overview

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.

Background

▶ Watch: What is an authenticated dictionary: lookups with proofs (0:30)

An authenticated dictionary extends a standard key-value dictionary (like Python's dict or C++'s map) with cryptographic guarantees. When you look up a key, you receive not just the value but a proof that this is the correct value for this key at this point in time. The proof is verified against a commitment -- a compact representation of the dictionary's state, analogous to a hash or checksum over the entire data structure.

The practical importance of authenticated dictionaries has grown dramatically with deployments in key transparency systems. Meta rolled out key transparency for WhatsApp in 2023, and Apple deployed it for iMessage around the same time. In these systems, the key is a phone number and the value is the cryptographic material needed to start an encrypted conversation with the genuine owner. The authenticated dictionary ensures that a server cannot substitute a malicious key without detection.

Other applications include binary transparency (verifying that software releases are genuine and up-to-date), revocation transparency (checking whether TLS certificates have been revoked), database and filesystem integrity, blockchain state (mapping account identifiers to balances), and news transparency (verifying that a news article is the same version others are reading).

Key Findings

▶ Watch: Applications: binary transparency, revocation, blockchain, news (3:30)

Five trust models identified: The survey identifies five distinct trust models for authenticated dictionary deployments: private outsource storage (backing up personal data to the cloud), public outsource storage (outsourcing data access APIs, e.g., DMV records), self-sovereign (multiple entities sharing a log, e.g., binary transparency), audited transparency (participants observe but lack authorization mechanisms, e.g., key transparency), and full transparency (all participants can perform verify-update themselves, an open problem).

Three core security definitions: The survey maps three fundamental security definitions and their relationships, providing a unified framework for comparing the security guarantees of different constructions.

Performance dichotomy: All 30 surveyed constructions fall into one of two groups: either both lookup and update are O(log n), or lookup is O(1) but update is O(n). No construction achieves constant-time lookup with sub-linear update, suggesting a possible fundamental trade-off.

Trust does not buy performance: Counterintuitively, constructions designed for trusted data sources do not achieve better asymptotic performance than those designed for untrusted sources. More trust in the system does not translate to more efficient constructions, based on the surveyed literature.

Two essential operations: Beyond simple lookup, two operations are critical for security: verify history (proving that authorized changes were executed and unauthorized changes were not, for a single key) and verify update (proving that the new commitment is the old commitment plus a specific sequence of updates, across all keys).

Technical Deep Dive

▶ Watch: Verify history and verify update: the essential security operations (5:30)

The complexity in authenticated dictionaries arises from handling updates. When the dictionary changes, a new commitment must be computed. Since proofs reference specific commitments, and commitments have already been distributed to users, the system must manage the transition from old commitments to new ones. This is where most of the engineering and theoretical complexity lies.

The verify history operation is key-specific: a key holder needs proof that when they authorize a change, the server executes it, and when they do not authorize a change, the server does not perform one. This requires tracking the history of a specific key across commitment epochs.

The verify update operation is system-wide: someone must check that each new commitment is correctly derived from the previous commitment plus a legitimate sequence of updates. In practice, this is often offloaded to an auditor role because the operation can be expensive. Whether this auditor role can be eliminated -- by making verify-update efficient enough for all participants to perform -- is an open problem corresponding to the "full transparency" trust model.

The Merkle tree is the foundational construction, but naive Merkle tree implementations face challenges with updates. Each update changes the commitment, and the system must handle the coexistence of multiple commitment versions as proofs are distributed and verified by different participants at different times.

Demo / Proof of Concept

▶ Watch: Performance dichotomy: log-log vs constant-linear trade-off (10:30)

As a Systematization of Knowledge paper, the contribution is the survey itself rather than a specific implementation. The unified framework of trust models, security definitions, and construction taxonomy provides a reference for researchers and practitioners working with authenticated dictionaries. The asymptotic performance survey across 30 schemes reveals patterns that were not previously documented, including the lookup/update performance dichotomy and the counterintuitive finding about trust and performance.

Defensive Implications

▶ Watch: Open questions: incentivizing auditors and regulatory compliance (12:00)

For messaging platform security teams (Meta, Apple, Signal, and others deploying key transparency), this SoK provides the theoretical foundation for understanding the security guarantees and trade-offs of different authenticated dictionary constructions. The trust model framework helps teams identify which model applies to their deployment and what security properties they should verify.

For software supply chain security (binary transparency), the survey highlights the open problem of eliminating the auditor role. If verify-update can be made efficient enough for all participants, software consumers could independently verify that the binary they download is the genuine, latest release without trusting an auditor.

For certificate transparency practitioners, the connection between authenticated dictionaries and revocation transparency provides a unified view of how these systems relate to efforts like CTng (also presented at this conference).

For security architects evaluating authenticated dictionary deployments, the performance dichotomy (log-log vs. constant-linear) is a practical design constraint: you must choose between efficient lookups (important for user-facing operations) and efficient updates (important for system throughput). No known construction avoids this trade-off.

Key Takeaways

• Authenticated dictionaries are deployed in key transparency (WhatsApp, iMessage), binary transparency, and blockchain systems
• Five trust models and three core security definitions provide a unified framework for comparing constructions
• All 30 surveyed constructions exhibit a performance dichotomy: O(log n) lookup + O(log n) update, or O(1) lookup + O(n) update
• No known construction achieves constant-time lookup with sub-linear update, suggesting a fundamental trade-off
• The auditor role in transparency systems is a trust assumption that remains an open problem to eliminate
• More trust in the data source does not yield better asymptotic performance in known constructions

About the Speaker(s)

Harjasleen Malvai is a researcher specializing in applied cryptography, transparency systems, and authenticated data structures. The SoK survey spans 30 years of literature and 30 distinct constructions, reflecting deep engagement with both the theoretical foundations and practical deployments of cryptographic authenticated dictionaries.