Paper 2022/1292

Bet-or-Pass: Adversarially Robust Bloom Filters

Moni Naor, Weizmann Institute of Science
Noa Oved, Weizmann Institute of Science

A Bloom filter is a data structure that maintains a succinct and probabilistic representation of a set $S\subseteq U$ of elements from a universe $U$. It supports approximate membership queries. The price of the succinctness is allowing some error, namely false positives: for any $x\notin S$, it might answer `Yes' but with a small (non-negligible) probability. When dealing with such data structures in adversarial settings, we need to define the correctness guarantee and formalize the requirement that bad events happen infrequently and those false positives are appropriately distributed. Recently, several papers investigated this topic, suggesting different robustness definitions. In this work we unify this line of research and propose several robustness notions for Bloom filters that allow the adaptivity of queries. The goal is that a robust Bloom filter should behave like a random biased coin even against an adaptive adversary. The robustness definitions are expressed by the type of test that the Bloom filter should withstand. We explore the relationships between these notions and highlight the notion of Bet-or-Pass as capturing the desired properties of such a data structure.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2022
Foundations Bloom filter Information-theoretic cryptography Leakage Resilience
Contact author(s)
moni naor @ weizmann ac il
noaoved3 @ gmail com
2022-09-29: approved
2022-09-28: received
See all versions
Short URL
Creative Commons Attribution


      author = {Moni Naor and Noa Oved},
      title = {Bet-or-Pass: Adversarially Robust Bloom Filters},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1292},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.