# Adversarially Robust Bloom Filters: Privacy, Reductions, and Open Problems

arXiv: https://arxiv.org/abs/2501.15751 · HTML: https://mlsanity.com/paper/2501.15751/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 7 of its 32 references that are in the map.
- First posted on arXiv 27 Jan 2025.

## Builds on (most cited first, 7 of 7)

- [Bloom Filters, Adaptivity, and the Dictionary Problem](https://mlsanity.com/paper/1711.01616/) (2017)
- [Bloom Filters in Adversarial Environments](https://mlsanity.com/paper/1412.8356/) (2014)
- [Adaptive Cuckoo Filters](https://mlsanity.com/paper/1704.06818/) (2017)
- [Sampling and Reconstruction Using Bloom Filters](https://mlsanity.com/paper/1701.03308/) (2017)
- [Adversary Resilient Learned Bloom Filters](https://mlsanity.com/paper/2409.06556/) (2024)
- [Asymmetric Differential Privacy](https://mlsanity.com/paper/2103.00996/) (2021)
- [Adversarial Correctness and Privacy for Probabilistic Data Structures](https://mlsanity.com/paper/2209.06955/) (2022)

## Abstract (arXiv)

A Bloom filter is a space-efficient probabilistic data structure that represents a set S of elements from a larger universe U. This efficiency comes with a trade-off, namely, it allows for a small chance of false positives. When you query the Bloom filter about an element x, the filter will respond 'Yes' if x ∈ S. If x notin S, it may still respond 'Yes' with probability at most varepsilon. We investigate the adversarial robustness and privacy of Bloom filters, addressing open problems across three prominent frameworks: the game-based model of Naor-Oved-Yogev (NOY), the simulator-based model of Filic et. al., and learning-augmented variants. We prove the first formal connection between the Filic and NOY models, showing that Filic correctness implies AB-test resilience. We resolve a longstanding open question by proving that PRF-backed Bloom filters fail the NOY model's stronger BP-test. Finally, we introduce the first private Bloom filters with differential privacy guarantees, including constructions applicable to learned Bloom filters. Our taxonomy organizes the space of robustness and privacy guarantees, clarifying relationships between models and constructions.