DPBloomfilter: Securing Bloom Filters with Differential Privacy
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909998298169344 |
|---|---|
| author | Ke, Yekun Liang, Yingyu Sha, Zhizhou Shi, Zhenmei Song, Zhao Zhang, Jiahao |
| author_facet | Ke, Yekun Liang, Yingyu Sha, Zhizhou Shi, Zhenmei Song, Zhao Zhang, Jiahao |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_00693 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | DPBloomfilter: Securing Bloom Filters with Differential Privacy Ke, Yekun Liang, Yingyu Sha, Zhizhou Shi, Zhenmei Song, Zhao Zhang, Jiahao Cryptography and Security 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. |
| title | DPBloomfilter: Securing Bloom Filters with Differential Privacy |
| topic | Cryptography and Security |
| url | https://arxiv.org/abs/2502.00693 |