Title: Faster Data Structures Have Less Access Pattern Leakage

Abstract: We study how set membership data structures leak through their access patterns. A random set is stored, and an adaptive adversary issues membership queries that reveal both whether a queried element is in the set and where it sits in the data structure. We prove a hidden-subset lemma showing that, even after querying a constant fraction of the universe, the adversary cannot find substantially more set elements than random guessing would suggest; its advantage is bounded by the compressed lookup information exposed by the data structure. Our lemma yields concrete bounds for basically all standard constructions, such as cuckoo hashing, linear probing, and quadratic probing.