Paper 2024/754
Adversary Resilient Learned Bloom Filters
Abstract
The Learned Bloom Filter is a recently proposed data structure that combines the Bloom Filter with a Learning Model while preserving the Bloom Filter's one-sided error guarantees. Creating an adversary-resilient construction of the Learned Bloom Filter with provable guarantees is an open problem. We define a strong adversarial model for the Learned Bloom Filter. Our adversarial model extends an existing adversarial model designed for the Classical (i.e. not ``Learned'') Bloom Filter by prior work and considers computationally bounded adversaries that run in probabilistic polynomial time (PPT). Using our model, we construct an adversary-resilient variant of the Learned Bloom Filter called the Downtown Bodega Filter. We show that: if pseudo-random permutations exist, then an Adversary Resilient Learned Bloom Filter may be constructed with
Metadata
- Available format(s)
-
PDF
- Category
- Secret-key cryptography
- Publication info
- Preprint.
- Keywords
- Pseudorandom PermutationsAdversarial Artificial IntelligenceProbabilistic Data Structures
- Contact author(s)
-
abishop @ ccny cuny edu
hayder research @ gmail com - History
- 2025-01-23: last of 7 revisions
- 2024-05-16: received
- See all versions
- Short URL
- https://ia.cr/2024/754
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/754, author = {Allison Bishop and Hayder Tirmazi}, title = {Adversary Resilient Learned Bloom Filters}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/754}, year = {2024}, url = {https://eprint.iacr.org/2024/754} }