IACR News item: 08 June 2015
Moni Naor, Eylon Yogev
ePrint ReportA 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.
Additional news items may be found on the IACR news page.