2025/02/02 by Yang Ke, Yekun Ke, Ke, Yekun +10 · 1 voice
Computer Science · #Caching and Content Delivery #Cooperative Communication and Network Coding #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Internet Traffic Analysis and Secure E-voting #cs.CR
paper · pdf · doi:10.48550/arxiv.2502.00693
openalex publication_date 2025/02/02 · arxiv published 2025/02/02 · openalex created_date 2025/10/10 · arxiv updated 2026/01/23 · openalex updated_date 2026/07/28
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.