adversarial-resilient-filter · research · also Adversarial-resilient Bloom filter

Adversarial-resilient filter

An adversarial-resilient filter bounds an adversary's chance of predicting a false positive for a fresh nonmember after observing earlier query responses.

Model: Naor and Yogev's challenge key must be outside both the stored set and the prior query set; the adversary observes answers, not internal memory. Their paper separates computationally bounded and query-bounded adversaries. [1]

Boundary: this fresh-key guarantee does not by itself bound replay of an already discovered false positive. Broom-filter adaptivity permits repeated challenges under a different feedback model. [1] [2]

Relations

related

Broom filter, Bloom filter, Universal hashing

Citations

1. Naor and Yogev. Bloom Filters in Adversarial Environments. CRYPTO 2015. DOI: 10.1007/978-3-662-48000-7_28. Definitions 2.2 and 2.4. (accessed 2026-11-12)
2. Bender et al. Bloom Filters, Adaptivity, and the Dictionary Problem. FOCS 2018. DOI: 10.1109/FOCS.2018.00026. arXiv v3, sections 2-4. (accessed 2026-11-12)

Further reading

3. Hesela: fresh challenges, repeated queries and correction history (accessed 2026-11-12)

JSON: /data/terms/adversarial-resilient-filter.json