Welcome to the resource topic for 2022/1292
Title:
Bet-or-Pass: Adversarially Robust Bloom Filters
Authors: Moni Naor, Noa Oved
Abstract: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.
ePrint: https://eprint.iacr.org/2022/1292
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .