Bloom Filters in Adversarial Environments
Preprint
Abstract
A Bloom filter represents a set $S$ of elements approximately, by using fewer bits than a precise representation. The price for succinctness is allowing some errors: for any $x \in S$ it should always answer 'Yes', and for any $x \notin S$ it should answer 'Yes' only with small probability. The latter are called false positive errors. In this work we study the possibility of Bloom filters in a stronger setting than the usual one, where an adversary can adaptively choose a sequence of queries according to previous results after the Bloom filter has been initialized. We consider both efficient adversaries (that run in polynomial-time) and computationally unbounded adversaries that are only bounded in the amount of queries they can make. We define a Bloom filter that maintains its error probability in this setting and say it is adversarial resilient. We show that non-trivial (memory-wise) adversarial resilient Bloom filters against computationally bounded adversaries exist if and only if one-way functions exist. The resulting construction is based on one-way permutations and is quite efficient and the proof of the necessity of one-way functions relies on the framework of adaptively changing distributions. For an unbounded adversary we show that there exist an $O(n\log{\frac{1}{\varepsilon}} + t)$ bits Bloom filter secure against $t$ queries (where $n$ is the set size and $\varepsilon$ is the false positive rate of the Bloom filter); in comparison, $n\log{\frac{1}{\varepsilon}}$ is the best possible under a non-adaptive adversary.
Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a StashAlgorithmica, 2013
- Hardness Preserving Reductions via Cuckoo Hashing2013
- Enhancing Collaborative Spam Detection with Bloom Filters2006
- Hierarchical Bloom filter arrays (HBA): a novel, scalable metadata management system for large cluster-based storage2005
- Network Applications of Bloom Filters: A SurveyInternet Mathematics, 2004
- Summary cache: a scalable wide-area Web cache sharing protocolIEEE/ACM Transactions on Networking, 2000
- On the Construction of Pseudorandom Permutations: Luby—Rackoff RevisitedJournal of Cryptology, 1999
- An algorithm for approximate membership checking with application to password securityInformation Processing Letters, 1994
- Cryptographic Primitives Based on Hard Learning Problems1994
- Clocked adversaries for hashingAlgorithmica, 1993