提出首个满足差分隐私的抗对抗性布隆过滤器，解决长期开放问题。
Adversarially Robust Bloom Filters: Privacy, Reductions, and Open Problems
- 建立两种安全模型间的首次形式化关联，揭示正确性与鲁棒性关系。
- 证明基于伪随机函数的布隆过滤器在强测试中不满足安全性要求。
- 为学习型布隆过滤器设计可验证的差分隐私构造，适合隐私敏感场景。
布隆过滤器是一种空间高效的概率数据结构，用于表示来自大集合U的元素集合S。其效率以一定的误报率ε为代价——当查询元素x时，若x∈S则返回‘是’；若x∉S，仍可能以至多ε的概率返回‘是’。本文研究布隆过滤器在三种主流框架下的对抗鲁棒性与隐私性：Naor-Oved-Yogev（NOY）的游戏模型、Filic等人的模拟器模型，以及学习增强型变体。我们首次建立了Filic模型与NOY模型之间的形式化联系，证明了Filic正确性蕴含AB测试鲁棒性。解决了长期悬而未决的问题：基于伪随机函数的布隆过滤器无法通过NOY模型中的更强的BP测试。最后，我们提出首个具备差分隐私保证的私密布隆过滤器，包括适用于学习型布隆过滤器的构造。我们的分类体系梳理了鲁棒性与隐私保证之间的关系，厘清了各模型与构造间的联系。
原文摘要 · Abstract (English)
A Bloom filter is a space-efficient probabilistic data structure that represents a set $S$ of elements from a larger universe $U$. This efficiency comes with a trade-off, namely, it allows for a small chance of false positives. When you query the Bloom filter about an element x, the filter will respond 'Yes' if $x \in S$. If $x \notin S$, it may still respond 'Yes' with probability at most $\varepsilon$. We investigate the adversarial robustness and privacy of Bloom filters, addressing open problems across three prominent frameworks: the game-based model of Naor-Oved-Yogev (NOY), the simulator-based model of Filic et. al., and learning-augmented variants. We prove the first formal connection between the Filic and NOY models, showing that Filic correctness implies AB-test resilience. We resolve a longstanding open question by proving that PRF-backed Bloom filters fail the NOY model's stronger BP-test. Finally, we introduce the first private Bloom filters with differential privacy guarantees, including constructions applicable to learned Bloom filters. Our taxonomy organizes the space of robustness and privacy guarantees, clarifying relationships between models and constructions.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。