可验证性的代价与对抗鲁棒布隆过滤器

### 可验证性的代价与对抗鲁棒布隆过滤器 #### 可验证性相关概念 在可验证性相关的研究中，有一系列特定的操作和定理。首先是一些基本操作步骤： 1. 从群 \(G\) 中选取一个生成元 \(g\)。 2. 从 \(Z_p^t\) 中随机选取 \((z_1, \ldots, z_t)\)。 3. 计算 \(a_1 := f_{A1}(z_1, \ldots, z_t), \ldots, a_{q1} := f_{Aq1}(z_1, \ldots, z_t)\)。 4. 计算 \(b_1 := f_{B1}(z_1, \ldots, z_t), \ldots, b_{q2} := f_{Bq2}(z_1, \ldots, z_t)\)。 5. 返回 \((g, g^{a_1}, \ldots, g^{a_{q1}}, e(g, g)^{b_1}, \ldots, e(g, g)^{b_{q2}})\)。 这里定义了 \(d_{NICA} = \max\{\deg f_{A1}, \ldots, \deg f_{Aq1}, \deg f_{B1}, \ldots, \deg f_{Bq2}\}\)，称 \(d_{NICA}\) 为 NICA 的度，\(q = 1 + q_1 + q_2\) 为 NICA 的大小。 有如下定理：设 \(vuf\) 是一个参数化的有理可验证随机函数（VUF），其评估度 \(d_{vuf} \in O(1)\)。设 NICA 是一个度为 \(d_{NICA} \in poly(\lambda)\) 且大小 \(q \leq \sqrt{\log \log(w)}\)（对于某个 \(w \in poly(\lambda)\)）的 Uber - 假设。如果 NICA 是困难的，并且 \(Q > 2\cdot(1 + \log \log w)\cdot w^2 \log(d_{vuf} + 1)\)，那么不存在通用的归约方法可以将一个针对 \(vuf\) 的弱 \(Q\) - 选择性不可预测性的敌手转化为一个 NICA 求解器。 该定理证明的核心思想在于，由于归约是代数且通用的，每个群元素的代数解释给出了一个环同态，它将群元素的表示映射到 Uber - 假设 NICA 的变量 \(Z_1, \ldots, Z_t\) 的多项式。对于敌手查询的每个 \(x \in Z_p\)，归约必须以某种方式选择这个环同态，使得多项式等式系统 \(S_x\) 得到满足。由于 \(vuf\) 是常数度参数化的，\(S_x\) 本身多项式依赖于 \(x\)。因此，如果 \(S_x\) 对于太多的 \(x \in Z_p\) 是可满足的，那么它对于每个 \(x \in Z_p\) 都必须是可满足的，并且 \(S_{x_0}\) 的解可以通过元归约仅用线性代数计算出来。所以，如果元归约可以进行太多查询，它就可以自行预测挑战查询 \(x_0\) 的像。 #### 布隆过滤器基础 布隆过滤器是一种数据结构，它维护一个来自全集 \(U\) 的集合 \(S \subseteq U\) 的简洁且概率性的表示。它支持近似成员查询，对于任何 \(x \in S\)，布隆过滤器必须回答 “Yes”，而对于任何 \(x \in U \setminus S\)，它应该回答 “No”，但允许有一个小的错误概率（最多为 \(\varepsilon\)），即可能回答 “Yes”，也就是存在假阳性，但不存在假阴性。 布隆过滤器的优点是构建所需的内存小，查询时间快，这使得它在各种应用中极具吸引力。但代价是存在一定的假阳性率，即不在集合中的元素可能被声明为在集合中。假阳性会影响性能，例如可能导致不必要的磁盘访问、未标记为垃圾邮件的垃圾邮件以及允许拼写错误的单词等。而且，如果想要节省空间，假阳性率就不能忽略不计。 #### 布隆过滤器的静态分析与适应性挑战 传统上，布隆过滤器的正确性主要是在静态分析下进行的，即先固定一个查询 \(x\)，然后计算内部随机性上的错误概率。然而，当敌手根据先前查询的响应自适应地选择下一个查询时，情况就变得复杂了。敌手可能会利用先前查询的响应泄露的关于数据结构内部状态或使用的随机位的信息，来增加假阳性率。 例如，在 Web 缓存共享中，代理使用布隆过滤器来表示其缓存内容。当代理收到网页请