Harjasleen Malvai (University of Illinois, Urbana-Champaign), Francesca Falzon (ETH Zürich), Andrew Zitek-Estrada (EPFL), Sarah Meiklejohn (University College London), Joseph Bonneau (NYU)
We systematize the research on authenticated dictionaries (ADs)—cryptographic data structures that enable applications such as key transparency, binary transparency, verifiable key-value stores, and integrity-preserving filesystems. First, we present a unified framework that captures the trust and threat assumptions behind five common deployment scenarios. Second, we distill and reconcile the diverse security definitions scattered across the literature, clarifying the guarantees they offer and when each is appropriate. Third, we develop a taxonomy of AD constructions and analyze their asymptotic costs, exposing a sharp dichotomy: every known scheme either incurs O(log n) time for both lookups and updates, or achieves O(1) for one operation only by paying O(n) for the other. Surprisingly, this barrier persists even when stronger trust assumptions are introduced, undermining the intuition that “more trust buys efficiency”. We conclude with application-driven research questions, including realistic auditing models and incentives for adoption in systems that today provide no verifiable integrity at all.