Adversarially Robust Bloom Filters: Monotonicity and Betting

Chen Lotan; Moni Naor

doi:10.62056/a3txom2hd

Adversarially Robust Bloom Filters: Monotonicity and Betting

Authors

Chen Lotan, Moni Naor

Chen Lotan

Weizmann Institute of Science, Rehovot, Israel
chen dot lotan at weizmann dot ac dot il

Moni Naor

Weizmann Institute of Science, Rehovot, Israel
moni dot naor at weizmann dot ac dot il

Keywords: Bloom filters adversarial settings pseudorandomness

Abstract

A Bloom filter is a probabilistic data structure designed to provide a compact representation of a set S of elements from a large universe U. The trade-off for this succinctness is allowing some errors. The Bloom filter efficiently answers membership queries: given any query x, if x is in S, it must answer ’Yes’; if x is not in S, it should answer ’Yes’ only with a small probability (at most ε).

Traditionally, the error probability of the Bloom filter is analyzed under the assumption that the query is independent of its internal randomness. However, Naor and Yogev (Crypto 2015) focused on the behavior of this data structure in adversarial settings; where the adversary may choose the queries adaptively. One particular challenge in this direction is to define rigorously the robustness of Bloom filters in this model.

In this work, we continue investigating the definitions of success of the adaptive adversary. Specifically, we focus on two notions proposed by Naor and Oved (TCC 2022) and examine the relationships between them. In particular, we highlight the notion of Bet-or-Pass as being stronger than others, such as Monotone-Test Resilience.

References

[ABD⁺21]

Noga Alon, Omri Ben-Eliezer, Yuval Dagan, Shay Moran, Moni Naor, and Eylon Yogev. Adversarial laws of large numbers and optimal regret in online classification. In STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021, pages 447–455. 2021. ACM. DOI: 10.1145/3406325.3451041

Google Scholar ePrint

[BFCG⁺18]

Michael A. Bender, Martin Farach-Colton, Mayank Goswami, Rob Johnson, Samuel McCauley, and Shikha Singh. Bloom Filters, Adaptivity, and the Dictionary Problem. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 182-193. 2018. DOI: 10.1109/FOCS.2018.00026

Google Scholar ePrint

[BHKN19]

Itay Berman, Iftach Haitner, Ilan Komargodski, and Moni Naor. Hardness-Preserving Reductions via Cuckoo Hashing. J. Cryptol., 32(2):361–392, 2019. DOI: 10.1007/S00145-018-9293-0

Google Scholar ePrint

[BJWY22]

Omri Ben-Eliezer, Rajesh Jayaram, David P. Woodruff, and Eylon Yogev. A Framework for Adversarially Robust Streaming Algorithms. J. ACM, 69(2):17:1–17:33, 2022. DOI: 10.1145/3498334

Google Scholar ePrint

[Blo70]

Burton H. Bloom. Space/Time Trade-offs in Hash Coding with Allowable Errors. Commun. ACM, 13(7):422–426, 1970. DOI: 10.1145/362686.362692

Google Scholar ePrint

[BLV19]

Elette Boyle, Rio LaVigne, and Vinod Vaikuntanathan. Adversarially Robust Property-Preserving Hash Functions. In 10th Innovations in Theoretical Computer Science Conference, ITCS 2019, January 10-12, 2019, San Diego, California, USA, volume 124 of LIPIcs, pages 16:1–16:20. 2019. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPICS.ITCS.2019.16

Google Scholar ePrint

[BM03]

Andrei Z. Broder and Michael Mitzenmacher. Survey: Network Applications of Bloom Filters: A Survey. Internet Math., 1(4):485–509, 2003. DOI: 10.1080/15427951.2004.10129096

Google Scholar ePrint

[BT24]

Allison Bishop and Hayder Tirmazi. Adversary Resilient Learned Bloom Filters. IACR Cryptol. ePrint Arch., 2024.

Google Scholar ePrint

[BY20]

Omri Ben-Eliezer and Eylon Yogev. The Adversarial Robustness of Sampling. In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems, PODS 2020, Portland, OR, USA, June 14-19, 2020, pages 49–62. 2020. ACM. DOI: 10.1145/3375395.3387643

Google Scholar ePrint

[CFG⁺78]

Larry Carter, Robert W. Floyd, John Gill, George Markowsky, and Mark N. Wegman. Exact and Approximate Membership Testers. In Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA, pages 59–65. 1978. ACM. DOI: 10.1145/800133.804332

Google Scholar ePrint

[CPS19]

David Clayton, Christopher Patton, and Thomas Shrimpton. Probabilistic Data Structures in Adversarial Environments. In Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, pages 1317–1334, New York, NY, USA. 2019. Association for Computing Machinery. DOI: 10.1145/3319535.3354235

Google Scholar ePrint

[DW03]

Martin Dietzfelbinger and Philipp Woelfel. Almost random graphs with simple hash functions. In Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA, pages 629–638. 2003. ACM. DOI: 10.1145/780542.780634

Google Scholar ePrint

[FPUV22]

Mia Filic, Kenneth G. Paterson, Anupama Unnikrishnan, and Fernando Virdia. Adversarial Correctness and Privacy for Probabilistic Data Structures. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, pages 1037–1050, New York, NY, USA. 2022. Association for Computing Machinery. DOI: 10.1145/3548606.3560621

Google Scholar ePrint

[Gol01]

Oded Goldreich. The Foundations of Cryptography - Volume 1: Basic Techniques. Cambridge University Press 2001. DOI: 10.1017/CBO9780511546891

Google Scholar ePrint

[KBC⁺18]

Tim Kraska, Alex Beutel, Ed H. Chi, Jeffrey Dean, and Neoklis Polyzotis. The Case for Learned Index Structures. In Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference 2018, Houston, TX, USA, June 10-15, 2018, pages 489–504. 2018. ACM. DOI: 10.1145/3183713.3196909

Google Scholar ePrint

[KMNS21]

Haim Kaplan, Yishay Mansour, Kobbi Nissim, and Uri Stemmer. Separating Adaptive Streaming from Oblivious Streaming Using the Bounded Storage Model. In Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, pages 94–121. 2021. Springer. DOI: 10.1007/978-3-030-84252-9_4

Google Scholar ePrint

[KS06]

Gil Kalai and Shmuel Safra. Threshold Phenomena and Influence: Perspectives from Mathematics, Computer Science, and Economics. In Allon G. Percus, Gabriel Istrate, and Cristopher Moore, editors, Computational Complexity and Statistical Physics, pages 25–62. Oxford University Press 2006.

Google Scholar ePrint

[Mit18]

Michael Mitzenmacher. A Model for Learned Bloom Filters and Optimizing by Sandwiching. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 462–471. 2018.

Google Scholar ePrint

[MU05]

Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press 2005. DOI: 10.1017/CBO9780511813603

Google Scholar ePrint

[NO22]

Moni Naor and Noa Oved. Bet-or-Pass: Adversarially Robust Bloom Filters. In Theory of Cryptography - 20th International Conference, TCC 2022, Chicago, IL, USA, November 7-10, 2022, Proceedings, Part II, volume 13748 of Lecture Notes in Computer Science, pages 777–808. 2022. Springer. DOI: 10.1007/978-3-031-22365-5_27

Google Scholar ePrint

[NPB21]

Sabuzima Nayak, Ripon Patgiri, and Angana Borah. A survey on the roles of Bloom Filter in implementation of the Named Data Networking. Computer Networks, 196:108232, 2021. DOI: https://doi.org/10.1016/j.comnet.2021.108232

Google Scholar ePrint

[NY15]

Moni Naor and Eylon Yogev. Bloom Filters in Adversarial Environments. In Advances in Cryptology - CRYPTO 2015 - 35th Annual Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2015, Proceedings, Part II, volume 9216 of Lecture Notes in Computer Science, pages 565–584. 2015. Springer. DOI: 10.1007/978-3-662-48000-7_28

Google Scholar ePrint

[Pag08]

Rasmus Pagh. Cuckoo Hashing. In Ming-Yang Kao, editor, Encyclopedia of Algorithms - 2008 Edition. Springer 2008. DOI: 10.1007/978-0-387-30162-4_97

Google Scholar ePrint

[PR04]

Rasmus Pagh and Flemming Friche Rodler. Cuckoo hashing. J. Algorithms, 51(2):122–144, 2004. DOI: 10.1016/J.JALGOR.2003.12.002

Google Scholar ePrint

[TRL12]

Sasu Tarkoma, Christian Esteve Rothenberg, and Eemil Lagerspetz. Theory and Practice of Bloom Filters for Distributed Systems. IEEE Commun. Surv. Tutorials, 14(1):131–155, 2012. DOI: 10.1109/SURV.2011.031611.00024

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/a3txom2hd

History

Submitted: 2025-01-13
Accepted: 2025-03-11
Published: 2025-04-08

How to cite

Chen Lotan and Moni Naor, Adversarially Robust Bloom Filters: Monotonicity and Betting. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a3txom2hd.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{10.62056/a3txom2hd,
         author={Chen Lotan and Moni Naor},
         title={Adversarially Robust Bloom Filters: Monotonicity and Betting},
         volume={2},
         number={1},
         year={2025},
         date={2025-04-08},
         issn={3006-5496},
         doi={10.62056/a3txom2hd},
         journal={{IACR} Communications in Cryptology},
         publisher={International Association for Cryptologic Research}
}

TY  - JOUR
AU  - Chen Lotan
AU  - Moni Naor
PY  - 2025
TI  - Adversarially Robust Bloom Filters: Monotonicity and Betting
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 2
IS  - 1
DO  - 10.62056/a3txom2hd
UR  - https://doi.org/10.62056/a3txom2hd
AB  - <p>A Bloom filter is a probabilistic data structure designed to provide a compact representation of a set S of elements from a large universe U. The trade-off for this succinctness is allowing some errors. The Bloom filter efficiently answers membership queries: given any query x, if x is in S, it must answer ’Yes’; if x is not in S, it should answer ’Yes’ only with a small probability (at most ε).</p><p>Traditionally, the error probability of the Bloom filter is analyzed under the assumption that the query is independent of its internal randomness. However, Naor and Yogev (Crypto 2015) focused on the behavior of this data structure in adversarial settings; where the adversary may choose the queries adaptively. One particular challenge in this direction is to define rigorously the robustness of Bloom filters in this model.</p><p>In this work, we continue investigating the definitions of success of the adaptive adversary. Specifically, we focus on two notions proposed by Naor and Oved (TCC 2022) and examine the relationships between them. In particular, we highlight the notion of Bet-or-Pass as being stronger than others, such as Monotone-Test Resilience. </p>
ER  -

Chen Lotan and Moni Naor, Adversarially Robust Bloom Filters: Monotonicity and Betting. IACR Communications in Cryptology, vol. 2, no. 1, Apr 08, 2025, doi: 10.62056/a3txom2hd.