A Privacy Model for Classical & Learned Bloom Filters

• URL: http://arxiv.org/abs/2501.15751v1
• Date: Mon, 27 Jan 2025 03:35:25 GMT
• Title: A Privacy Model for Classical & Learned Bloom Filters
• Authors: Hayder Tirmazi,
• Abstract summary: The Classical Bloom Filter (CBF) is a class of Probabilistic Data Structures (PDS) The Learned Bloom Filter (LBF) is a recently proposed class of PDS that combines the Classical Bloom Filter with a Learning Model.
• Score: 0.0
• License:
• Abstract: The Classical Bloom Filter (CBF) is a class of Probabilistic Data Structures (PDS) for handling Approximate Query Membership (AMQ). The Learned Bloom Filter (LBF) is a recently proposed class of PDS that combines the Classical Bloom Filter with a Learning Model while preserving the Bloom Filter's one-sided error guarantees. Bloom Filters have been used in settings where inputs are sensitive and need to be private in the presence of an adversary with access to the Bloom Filter through an API or in the presence of an adversary who has access to the internal state of the Bloom Filter. Prior work has investigated the privacy of the Classical Bloom Filter providing attacks and defenses under various privacy definitions. In this work, we formulate a stronger differential privacy-based model for the Bloom Filter. We propose constructions of the Classical and Learned Bloom Filter that satisfy $(\epsilon, 0)$-differential privacy. This is also the first work that analyses and addresses the privacy of the Learned Bloom Filter under any rigorous model, which is an open problem.

Related papers

• Cascaded Learned Bloom Filter for Optimal Model-Filter Size Balance and Fast Rejection [12.555117983678624]
  We propose the Cascaded Learned Bloom Filter (CLBF) to address these issues. Our dynamic programming-based optimization automatically selects configurations that achieve an optimal balance between the model and filter sizes. Experiments on real-world datasets show that CLBF reduces memory usage by up to 24% and decreases reject time by up to 14 times compared to state-of-the-art learned Bloom filters.
  arXiv  Detail & Related papers  (2025-02-06T01:05:41Z)
• DPBloomfilter: Securing Bloom Filters with Differential Privacy [17.002793355495136]
  The DPBloomfilter integrates the classical differential privacy mechanism, specifically the Random Response technique, into the Bloom filter. It offers robust privacy guarantees under the same running complexity as the standard Bloom filter. This is the first work to provide differential privacy guarantees for the Bloom filter for membership query problems.
  arXiv  Detail & Related papers  (2025-02-02T06:47:50Z)
• Adversary Resilient Learned Bloom Filters [0.4910937238451484]
  We define a strong adversarial model for the Learned Bloom Filter. Using our model, we construct an adversary-resilient variant of the Learned Bloom Filter called Downtown Bodega Filter.
  arXiv  Detail & Related papers  (2024-09-10T14:37:43Z)
• Privacy Side Channels in Machine Learning Systems [87.53240071195168]
  We introduce privacy side channels: attacks that exploit system-level components to extract private information. For example, we show that deduplicating training data before applying differentially-private training creates a side-channel that completely invalidates any provable privacy guarantees. We further show that systems which block language models from regenerating training data can be exploited to exfiltrate private keys contained in the training set.
  arXiv  Detail & Related papers  (2023-09-11T16:49:05Z)
• Compressing (Multidimensional) Learned Bloom Filters [7.6058140480517356]
  A Bloom filter reveals if an element is not included in the underlying set or is included with a certain error rate. Deep learning models are used to solve this membership testing problem. We show that the benefits of learned Bloom filters are apparent only when considering a vast amount of data.
  arXiv  Detail & Related papers  (2022-08-05T07:54:48Z)
• Fully Adaptive Composition in Differential Privacy [53.01656650117495]
  Well-known advanced composition theorems allow one to query a private database quadratically more times than basic privacy composition would permit. We introduce fully adaptive composition, wherein both algorithms and their privacy parameters can be selected adaptively. We construct filters that match the rates of advanced composition, including constants, despite allowing for adaptively chosen privacy parameters.
  arXiv  Detail & Related papers  (2022-03-10T17:03:12Z)
• On the Choice of General Purpose Classifiers in Learned Bloom Filters: An Initial Analysis Within Basic Filters [0.41998444721319217]
  Several versions of Bloom Filters have been considered, yielding advantages over classic Filters. Each of them uses a classifier, which is the Learned part of the data structure. No systematic study of which specific classifier to use in which circumstances is available.
  arXiv  Detail & Related papers  (2021-12-13T11:15:41Z)
• Understanding Clipping for Federated Learning: Convergence and Client-Level Differential Privacy [67.4471689755097]
  This paper empirically demonstrates that the clipped FedAvg can perform surprisingly well even with substantial data heterogeneity. We provide the convergence analysis of a differential private (DP) FedAvg algorithm and highlight the relationship between clipping bias and the distribution of the clients' updates.
  arXiv  Detail & Related papers  (2021-06-25T14:47:19Z)
• Unsharp Mask Guided Filtering [53.14430987860308]
  The goal of this paper is guided image filtering, which emphasizes the importance of structure transfer during filtering. We propose a new and simplified formulation of the guided filter inspired by unsharp masking. Our formulation enjoys a filtering prior to a low-pass filter and enables explicit structure transfer by estimating a single coefficient.
  arXiv  Detail & Related papers  (2021-06-02T19:15:34Z)
• Data Agnostic Filter Gating for Efficient Deep Networks [72.4615632234314]
  Current filter pruning methods mainly leverage feature maps to generate important scores for filters and prune those with smaller scores. In this paper, we propose a data filter pruning method that uses an auxiliary network named Dagger module to induce pruning. In addition, to help prune filters with certain FLOPs constraints, we leverage an explicit FLOPs-aware regularization to directly promote pruning filters toward target FLOPs.
  arXiv  Detail & Related papers  (2020-10-28T15:26:40Z)
• Training Interpretable Convolutional Neural Networks by Differentiating Class-specific Filters [64.46270549587004]
  Convolutional neural networks (CNNs) have been successfully used in a range of tasks. CNNs are often viewed as "black-box" and lack of interpretability. We propose a novel strategy to train interpretable CNNs by encouraging class-specific filters.
  arXiv  Detail & Related papers  (2020-07-16T09:12:26Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.