Paper 2015/543
Bloom Filters in Adversarial Environments
Moni Naor and Eylon Yogev
Abstract
Many efficient data structures use randomness, allowing them to improve upon deterministic ones. Usually, their efficiency and correctness are analyzed using probabilistic tools under the assumption that the inputs and queries are independent of the internal randomness of the data structure. In this work, we consider data structures in a more robust model, which we call the adversarial model. Roughly speaking, this model allows an adversary to choose inputs and queries adaptively according to previous responses. Specifically, we consider a data structure known as "Bloom filter" and prove a tight connection between Bloom filters in this model and cryptography. 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. In the adversarial model, we consider both efficient adversaries (that run in polynomial time) and computationally unbounded adversaries that are only bounded in the number of queries they can make. For computationally bounded adversaries, we show that nontrivial (memorywise) Bloom filters exist if and only if oneway functions exist. For unbounded adversaries we show that there exists a Bloom filter for sets of size $n$ and error $\varepsilon$, that is secure against $t$ queries and uses only $O(n \log{\frac{1}{\varepsilon}}+t)$ bits of memory. In comparison, $n\log{\frac{1}{\varepsilon}}$ is the best possible under a nonadaptive adversary.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 A minor revision of an IACR publication in CRYPTO 2015
 Keywords
 Bloom filterOne way functionsCuckoo hashing
 Contact author(s)
 eylony @ gmail com
 History
 20190129: revised
 20150608: received
 See all versions
 Short URL
 https://ia.cr/2015/543
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/543, author = {Moni Naor and Eylon Yogev}, title = {Bloom Filters in Adversarial Environments}, howpublished = {Cryptology ePrint Archive, Paper 2015/543}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/543}}, url = {https://eprint.iacr.org/2015/543} }