Paper 2024/754

Adversary Resilient Learned Bloom Filters

Allison Bishop, City College of New York, Proof Trading
Hayder Tirmazi, City College of New York
Abstract

Creating an adversary resilient Learned Bloom filter with provable guarantees is an open problem. We define a strong adversarial model for the Learned Bloom Filter. We also construct two adversary resilient variants of the Learned Bloom Filter called the Uptown Bodega Filter and the Downtown Bodega Filter. Our adversarial model extends an existing adversarial model designed for the classical (i.e not ``learned'') Bloom Filter by Naor and Yogev and considers computationally bounded adversaries that run in probabilistic polynomial time (PPT). We show that if pseudo-random permutations exist, then a secure Learned Bloom Filter may be constructed with $\lambda$ extra bits of memory and at most one extra pseudo-random permutation in the critical path. We further show that, if pseudo-random permutations exist, then a high utility Learned Bloom Filter may be constructed with $2\lambda$ extra bits of memory and at most one extra pseudo-random permutation in the critical path. Finally, we construct a hybrid adversarial model for the case where a fraction of the workload is chosen by an adversary. We show realistic scenarios where using the Downtown Bodega Filter gives better performance guarantees compared to alternative approaches in this model.

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
tirmazi42 @ gmail com
History
2024-05-20: approved
2024-05-16: received
See all versions
Short URL
https://ia.cr/2024/754
License
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2024/754}},
      url = {https://eprint.iacr.org/2024/754}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.