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

DirtyFree: Simplified Data-Oriented Programming in the Linux Kernel

Yoochan Lee (Max Planck Institute for Security and Privacy), Hyuk Kwon (Theori, Inc.), Thorsten Holz (Max Planck Institute for Security and Privacy)

Read More

Memory Band-Aid: A Principled Rowhammer Defense-in-Depth

Carina Fiedler (Graz University of Technology), Jonas Juffinger (Graz University of Technology), Sudheendra Raghav Neela (Graz University of Technology), Martin Heckel (Hof University of Applied Sciences), Hannes Weissteiner (Graz University of Technology), Abdullah Giray Yağlıkçı (ETH Zürich), Florian Adamsky (Hof University of Applied Sciences), Daniel Gruss (Graz University of Technology)

Read More

LLMBisect: Breaking Barriers in Bug Bisection with A Comparative...

Zheng Zhang (University of California, Riverside), Haonan Li (University of California, Riverside), Xingyu Li (University of California, Riverside), Hang Zhang (Indiana University Bloomington), Zhiyun Qian (University of California, Riverside)

Read More