DPBloomfilter: Securing Bloom Filters with Differential Privacy

• URL: http://arxiv.org/abs/2502.00693v1
• Date: Sun, 02 Feb 2025 06:47:50 GMT
• Title: DPBloomfilter: Securing Bloom Filters with Differential Privacy
• Authors: Yekun Ke, Yingyu Liang, Zhizhou Sha, Zhenmei Shi, Zhao Song,
• Abstract summary: 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.
• Score: 17.002793355495136
• License:
• Abstract: The Bloom filter is a simple yet space-efficient probabilistic data structure that supports membership queries for dramatically large datasets. It is widely utilized and implemented across various industrial scenarios, often handling massive datasets that include sensitive user information necessitating privacy preservation. To address the challenge of maintaining privacy within the Bloom filter, we have developed the DPBloomfilter. This innovation integrates the classical differential privacy mechanism, specifically the Random Response technique, into the Bloom filter, offering robust privacy guarantees under the same running complexity as the standard Bloom filter. Through rigorous simulation experiments, we have demonstrated that our DPBloomfilter algorithm maintains high utility while ensuring privacy protections. To the best of our knowledge, this is the first work to provide differential privacy guarantees for the Bloom filter for membership query problems.

Related papers

• A Privacy Model for Classical & Learned Bloom Filters [0.0]
  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.
  arXiv  Detail & Related papers  (2025-01-27T03:35:25Z)
• Activity Recognition on Avatar-Anonymized Datasets with Masked Differential Privacy [64.32494202656801]
  Privacy-preserving computer vision is an important emerging problem in machine learning and artificial intelligence. We present anonymization pipeline that replaces sensitive human subjects in video datasets with synthetic avatars within context. We also proposeMaskDP to protect non-anonymized but privacy sensitive background information.
  arXiv  Detail & Related papers  (2024-10-22T15:22:53Z)
• 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)
• Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification [54.1447806347273]
  Amplification by subsampling is one of the main primitives in machine learning with differential privacy. We propose the first general framework for deriving mechanism-specific guarantees. We analyze how subsampling affects the privacy of groups of multiple users.
  arXiv  Detail & Related papers  (2024-03-07T19:36:05Z)
• Privacy-Preserving Matrix Factorization for Recommendation Systems using Gaussian Mechanism [2.84279467589473]
  We propose a privacy-preserving recommendation system based on the differential privacy framework and matrix factorization. As differential privacy is a powerful and robust mathematical framework for designing privacy-preserving machine learning algorithms, it is possible to prevent adversaries from extracting sensitive user information.
  arXiv  Detail & Related papers  (2023-04-11T13:50:39Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  We study the space complexity of the two related fields of differential privacy and adaptive data analysis. We show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy. The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries.
  arXiv  Detail & Related papers  (2023-02-11T14:45:31Z)
• A Critical Analysis of Classifier Selection in Learned Bloom Filters [0.3359875577705538]
  "Complexity" of the data used to build the filter might heavily impact on its performance. We propose a novel methodology, supported by software, for designing, analyzing and implementing Learned Bloom Filters. Experiments show that the proposed methodology and the supporting software are valid and useful.
  arXiv  Detail & Related papers  (2022-11-28T17:17:18Z)
• Algorithms with More Granular Differential Privacy Guarantees [65.3684804101664]
  We consider partial differential privacy (DP), which allows quantifying the privacy guarantee on a per-attribute basis. In this work, we study several basic data analysis and learning tasks, and design algorithms whose per-attribute privacy parameter is smaller that the best possible privacy parameter for the entire record of a person.
  arXiv  Detail & Related papers  (2022-09-08T22:43:50Z)
• 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)
• Private Reinforcement Learning with PAC and Regret Guarantees [69.4202374491817]
  We design privacy preserving exploration policies for episodic reinforcement learning (RL) We first provide a meaningful privacy formulation using the notion of joint differential privacy (JDP) We then develop a private optimism-based learning algorithm that simultaneously achieves strong PAC and regret bounds, and enjoys a JDP guarantee.
  arXiv  Detail & Related papers  (2020-09-18T20:18:35Z)

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.