# Adversary Resilient Learned Bloom Filters

arXiv: https://arxiv.org/abs/2409.06556 · HTML: https://mlsanity.com/paper/2409.06556/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Sep 2024.

## Built on by (most cited first, 2 of 2)

- [Context Compaction Theory](https://mlsanity.com/paper/2608.01326/) (2026)
- [Adversarially Robust Bloom Filters: Privacy, Reductions, and Open Problems](https://mlsanity.com/paper/2501.15751/) (2025)

## Abstract (arXiv)

A learned Bloom filter (LBF) combines a classical Bloom filter (CBF) with a learning model to reduce the amount of memory needed to represent a given set while achieving a target false positive rate (FPR). Provable security against adaptive adversaries that advertently attempt to increase FPR has been studied for CBFs, but not for LBFs. In this paper, we close this gap and show how to achieve adaptive security for LBFs. In particular, we define several adaptive security notions capturing varying degrees of adversarial control, including full and partial adaptivity, in addition to LBF extensions of existing adversarial models for CBFs, including the Always-Bet and Bet-or-Pass notions. We propose two secure LBF constructions, PRP-LBF and Cuckoo-LBF, and formally prove their security under these models assuming the existence of one-way functions. Based on our analysis and use case evaluations, our constructions achieve strong security guarantees while maintaining competitive FPR and memory overhead.