2024/09/10 by Almashaqbeh, Ghada, Allison Bishop, Bishop, Allison +2 · 1 citation
Computer Science · #Anomaly Detection Techniques and Applications #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Network Security and Intrusion Detection
paper · pdf · doi:10.48550/arxiv.2409.06556
openalex publication_date 2024/09/10 · openalex created_date 2024/10/12 · openalex updated_date 2026/07/28
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.