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.

View More Papers

ANONYCALL: Enabling Native Private Calling in Mobile Networks

Hexuan Yu (Virginia Polytechnic Institute and State University), Chaoyu Zhang (Virginia Polytechnic Institute and State University), Yang Xiao (University of Kentucky), Angelos D. Keromytis (Georgia Institute of Technology), Y. Thomas Hou (Virginia Polytechnic Institute and State University), Wenjing Lou (Virginia Polytechnic Institute and State University)

Read More

Bounded Autonomy in the SOC: Mitigating Hallucinations in Agentic...

Samuel Addington (California State University Long Beach)

Read More

Revealing The Secret Power: How Algorithms Can Influence Content...

Alessandro Galeazzi (University of Padua), Pujan Paudel (Boston University), Mauro Conti (University of Padua and Orebro University), Emiliano De Cristofaro (University of California, Riverside), Gianluca Stringhini (Boston University)

Read More