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 not in 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 amount of queries they can make. For computationally bounded adversaries, we show that non-trivial (memory-wise) Bloom filters exist if and only if one-way functions exist. For unbounded adversaries we show that there exists a Bloom filter for sets of size n and error eps, that is secure against t queries and uses only O(n*log(1/eps) + t) bits of memory. In comparison, n*log(1/eps) is the best possible under a non-adaptive adversary.Category / Keywords: foundations / Bloom filter, One way functions, Cuckoo hashing Original Publication (with minor differences): IACR-CRYPTO-2015 Date: received 3 Jun 2015 Contact author: eylony at gmail com Available format(s): PDF | BibTeX Citation Version: 20150608:212334 (All versions of this report) Short URL: ia.cr/2015/543 Discussion forum: Show discussion | Start new discussion