Paper 2025/125

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

Hayder Tirmazi, City College of New York
Abstract

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 xS. If xS, it may still respond 'Yes' with probability at most ε. 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.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
Preprint.
Keywords
Bloom filterspseudorandomnessdifferential privacy
Contact author(s)
hayder research @ gmail com
History
2025-06-16: last of 3 revisions
2025-01-27: received
See all versions
Short URL
https://ia.cr/2025/125
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/125,
      author = {Hayder Tirmazi},
      title = {Adversarially Robust Bloom Filters: Privacy, Reductions, and Open Problems},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/125},
      year = {2025},
      url = {https://eprint.iacr.org/2025/125}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.