对抗鲁棒布隆过滤器：AB与BP概念及相关研究

### 对抗鲁棒布隆过滤器：AB与BP概念及相关研究 在数据处理和安全领域，布隆过滤器是一种常用的数据结构，而对抗鲁棒性是评估其性能的重要指标。本文将深入探讨布隆过滤器的AB和BP概念、相关的计算假设与单向函数，以及一些相关的研究工作和开放问题。 #### 1. AB与BP概念的差异：以惊喜考试悖论为例 为了更好地理解AB和BP概念的差异，我们可以借助著名的惊喜考试（或意外绞刑）悖论。假设一位老师宣布将在接下来的六天内随机选择一天进行“惊喜考试”。每天晚上，学生可以下注预测考试是否会在第二天举行。如果预测正确，学生将赢得5美元；如果预测错误，将输掉1美元。并且学生只能下注一次。 - **AB设置**：学生至少要在某一天下注。在这种情况下，面对随机选择的考试日期，学生的期望收益为0。 - **BP设置**：学生可以选择完全不下注。在这种情况下，学生可以等到最后一天，如果之前都没有考试，那么就可以确定考试在最后一天，此时下注的期望收益为5/6。 如果老师不是随机选择考试日期，而是采用其他分布，那么就需要更复杂的策略，但仍然是可行的。 #### 2. 计算假设与单向函数 Naor和Yogev证明了对计算受限的对手具有AB测试弹性的布隆过滤器与单向函数之间存在存在性等价关系。我们将此称为等价结果。接下来，我们探讨对于具有BP测试弹性的布隆过滤器，这种等价关系是否仍然成立。 - **简单方向**：具有BP测试弹性的布隆过滤器意味着存在单向函数。这可以通过BP测试对AB测试的影响直接得出。 - **较难方向**：我们展示了一种基于单向函数存在性的布隆过滤器构造的修改方法，并证明它具有BP测试弹性，从而证明了所需的等价关系。 此外，我们还研究了较弱的鲁棒性概念是否意味着单向函数的存在。结果表明，如果单向函数不存在，那么任何非平凡的布隆过滤器都会在期望计数测试和半自适应预测测试中失败。 #### 3. 相关工作 - **Naor和Yogev的工作**：他们是第一个考虑根据布隆过滤器的响应选择查询的自适应对手的研究者。他们通过与对手的游戏定义了布隆过滤器的对抗模型，对手只能通过预言机访问布隆过滤器，无法看到其内部随机性。对手的目标是找到一个从未查询过的假阳性元素。 - **Clayton、Patton和Shrimpton的工作**：他们分析了布隆过滤器以及其他数据结构（如计数布隆过滤器和计数最小草图）在对抗环境中的性能。他们分析了在一系列自适应查询中获得预定义数量的假阳性元素的概率，这与我们的期望计数测试类似。 - **Bender等人的工作**：他们指出假阳性概率的界限仅适用于单个固定查询，而一系列查询可能会有更高的假阳性率。他们主要关注对手重复假阳性查询的情况，并定义了一种自适应过滤器，该过滤器可以适应假阳性，即使对于已经查询并返回为假阳性的元素，重复查询的假阳性率也最多为ε。 - **其他相关工作**：Mitzenmacher等人讨论了自适应布谷鸟过滤器，Lee等人讨论了伸缩自适应过滤器（TAF）。此外，在流式算法文献中，也有对定义自适应环境中正确性问题的研究，如Hardt和Woodruff表明线性草图对自适应选择的输入本质上不鲁棒，而Ben - Eliezer等人提出了将非鲁棒流式算法转换为鲁棒算法的通用编译器。 #### 4. 开放问题 我们的工作留下了几个有趣的研究方向： - **单调性测试弹性与BP测试弹性的关系**：我们已经证明了一个方向，即BP测试弹性意味着单调性测试弹性，但另一个方向（单调性测试弹性是否意味着BP测试弹性）以及这两个概念是否可分离仍有待研究。 - **Bender等人的技术与我们结果的兼容性**：我们想知道是否可以构建一个对重复查询具有鲁棒性的BP安全布隆过滤器。 - **允许输出“不知道”（pass）的影响**：为了更好地捕捉决策游戏的位安全性，Micciancio和Walter允许对手输出一个bot，并重新定义了对手的优势。输出bot与BP测试中的pass非常相似，允许pass并重新定义优势可能会给出更好的概念。我们想知道这两个定义之间是否存在联系，以及我们的定义是否可以应用于更一般的设置。 #### 5. 模型和问题定义 对于一个全域U = [u]，我们给定一个包含n个元素的子集S ⊂ U。这个集合可以在布隆过滤器的整个生命周期内固定，也可以通过插入查询形成。在本文中，我们主要考虑集合S固定的情况，但我们的结果可以扩展到其他设置。 我们将布隆过滤器B = (B1, B2)建模为一个由两部分组成的数据结构： - **设置算法B1**：它是随机化的，以集合S为输入，输出S的压缩表示M。 - **查询算法B2**：它也可以是随机化的，以集合S的压缩表示M和一个查询元素x ∈ U为输入，输出一个响应，表示x是否属于S（对于x ∉ S，可能会出错）。 我们定义一个布隆过滤器为(n, ε)-布隆过滤器，如果对于合适全域U中所有大小为n的集合S，满足以下条件： 1. **完整性**：对于任何x ∈ S，Pr[B2(B1(S, x)) = 1] = 1。 2. **可靠性**：对于任何x ∉ S，Pr[B2(B1(S, x)) = 1] ≤ ε。 ##### 自适应游戏 定义1考虑的是单个固定输入元素x，概率是基于布隆过滤器的随机性。为了加强这个保证，我们考虑一个由对手自适应选择的t个输入元素的