论文标题
概率数据结构的对抗性正确性和隐私
Adversarial Correctness and Privacy for Probabilistic Data Structures
论文作者
论文摘要
我们研究概率数据结构（PD）在处理近似会员查询（AMQ）方面的安全性； AMQ-PD的突出例子是Bloom和Duckoo过滤器。 AMQ-PD越来越多地被部署在对手可以从仔细选择输入中获取受益的环境中，例如增加AMQ-PD的假阳性率。它们也用于在输入敏感的设置中使用，面对可以通过API访问AMQ-PD的对手或可以通过损害运行AMQ-PD的系统来学习其内部状态的对手。 我们开发了基于模拟的安全定义，这些定义讲述了AMQ-PD的正确性和隐私。我们的定义是一般的，并且适用于广泛的对抗设置。我们使用定义来分析Bloom过滤器和仅插入杜鹃滤波器的行为。我们表明，这些AMQ-PD可以通过在其构造中使用钥匙化的伪随机函数的替换或组成来保护这些AMQ-PD。我们还研究了对存储尺寸的实际影响，并计算提供了仅插入的杜鹃滤波器的安全实例。
We study the security of Probabilistic Data Structures (PDS) for handling Approximate Membership Queries (AMQ); prominent examples of AMQ-PDS are Bloom and Cuckoo filters. AMQ-PDS are increasingly being deployed in environments where adversaries can gain benefit from carefully selecting inputs, for example to increase the false positive rate of an AMQ-PDS. They are also being used in settings where the inputs are sensitive and should remain private in the face of adversaries who can access an AMQ-PDS through an API or who can learn its internal state by compromising the system running the AMQ-PDS. We develop simulation-based security definitions that speak to correctness and privacy of AMQ-PDS. Our definitions are general and apply to a broad range of adversarial settings. We use our definitions to analyse the behaviour of both Bloom filters and insertion-only Cuckoo filters. We show that these AMQ-PDS can be provably protected through replacement or composition of hash functions with keyed pseudorandom functions in their construction. We also examine the practical impact on storage size and computation of providing secure instances of Bloom and insertion-only Cuckoo filters.
