UltraFilter: A Privacy-Preserving Bloom Filter

Recent work by Reviriego et al. [12] has shown susceptibility to privacy leaks for elements stored in the Bloom Filter due to the possibility of recovery attacks despite the indirection (unlinkability) afforded by the underlying hash functions. As a result, we introduced a data structure known as UltraFilter to allow for approximate set membership checks without the pre-existing privacy issues in the standard Bloom filter by employing differential privacy. We provide a threefold contribution: First, we achieve tunable privacy by modifying the noise, ε, to adjust the reconstruction error that trades off utility for privacy protection in UltraFilter. Second, we provide a set of proofs to validate our formulation and a working implementation1 for easy replication. Finally, we demonstrate the usefulness of our formulation in an ablation study.