International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Noa Oved

Publications

Year
Venue
Title
2022
TCC
Bet-or-Pass: Adversarially Robust Bloom Filters
Moni Naor Noa Oved
A Bloom filter is a data structure that maintains a succinct and probabilistic representation of a set of elements from a universe. It supports approximate membership queries. The price of the succinctness is allowing some error, namely false positives: for any element not in the set, 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 try to 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 formalized by the type of test the Bloom filter should withstand. We then explore the relationships between these notions and highlight the notion of Bet-or-Pass as capturing the desired properties of such a data structure.

Coauthors

Moni Naor (1)