破解带后门随机预言机之异或组合器分析

### 破解带后门随机预言机之异或组合器分析 #### 1. 异或组合器概述 异或组合器定义为 \(C_{H_1,H_2}^{\oplus}(x) := H_1(x) \oplus H_2(x)\)，我们研究其在 2 - BRO 模型中与随机预言机 RO 的不可区分性。目标是证明存在一个模拟器 \(Sim := (Sim_{H_1}^{RO}, Sim_{H_2}^{RO}, Sim_{BD_1}^{RO}, Sim_{BD_2}^{RO})\)，使得任何进行 “合理” 数量查询的区分器都无法区分 \((C_{H_1,H_2}^{\oplus}, H_1, H_2, Bd_1, Bd_2)\) 和 \((RO, Sim_{H_1}^{RO}, Sim_{H_2}^{RO}, Sim_{BD_1}^{RO}, Sim_{BD_2}^{RO})\)。 #### 2. 模拟器设计 - **初始化**：假设初始值 \(hst_1 = hst_2 = hst_{RO} := \varnothing\)，\(\mu_1 = \mu_2 := U[M]^N\)，\(H_1, H_2 \leftarrow U[M]^N\)，\(q := 0\)，\(s := 0\)。 - **评估查询模拟**：模拟对 \(H_1\) 和 \(H_2\) 的评估查询较为直接。 - **后门查询模拟**：利用分解技术将高最小熵分布转换为有固定点且其余部分密集的分布。后门模拟器 \(Sim_{BD_1}\)（或 \(Sim_{BD_2}\)）在 \(H_1\)（或 \(H_2\)）的真值表上计算查询函数 \(f\)。为简化，考虑对手在切换到另一个后门预言机之前，对一个后门预言机进行 \(Q\) 次连续查询。在对一个后门预言机进行第 \(i\) 组 \(Q\) 次查询后，将泄露的后门信息转化为固定哈希函数的 \(p_i\) 行，使其余部分密集，且所得分布在统计上接近真实分布。 #### 3. 密度率与分布处理 - **密度率**：对于 \(H_1\) 后门查询后的分布使用奇数 \(i\) 的 \(\delta_i\)，对于 \(H_2\) 的分布使用偶数 \(i\) 的 \(\delta_i\)。这对于保持两个分布在整个表上的统计距离较小至关重要。 - **部分固定和部分密集分布的查找**：使用 FixRows 算法，输入分布 \(\mu_z\)、整数 \(p \in N\) 和集合 \(I_{prv} \in [N]\)，返回一个新分布，该分布在大小至多为 \(p + |I_{prv}|\) 的集合 \(I\) 上固定，其余部分为 \((1 - \delta)\) 密集，并给出集合 \(I\) 中元素的赋值集合 \(A\)。FixRows 算法内部调用细化分解算法。 #### 4. 一致性保证 当固定一个模拟 BRO 的行时，另一个模拟 BRO 的相同行必须以确保与 RO 一致的方式固定。例如，若 \(H_1(x)\) 被固定，模拟器 \(Sim_{BD_1}\) 会立即设置 \(H_2(x) := RO(x) \oplus H_1(x)\)，评估模拟器 \(Sim_{H_1}\) 和 \(Sim_{H_2}\) 也遵循类似策略。 #### 5. 统计距离分析 - **均匀分布与密集分布的统计距离**：设 \(U\) 为均匀分布，\(V\) 为 \((1 - \delta)\) 密集分布，都在域 \([M]^t\) 上，则 \(SD(U, V) \leq t \cdot \delta \cdot \log M\)。 - **证明**： \[ \begin{align*} SD(U, V) &= \sum_{z \in [M]^t} \max\{0, Pr[V = z] - Pr[U = z]\}\\ &= \sum_{z \in V^+} \max\{0, Pr[V = z] - Pr[U = z]\}\\ &= \sum_{z \in V^+} Pr[V = z] \cdot \max\{0, 1 - \frac{Pr[U = z]}{Pr[V = z]}\} \end{align*} \] 因为对于任何 \(z \in [M]^t\)，有 \(Pr[V = z] \leq M^{-(1 - \delta) \cdot t}\) 和 \(Pr[U = z] = M^{-t}\)，所以 \(SD(U, V) \leq 1 - M^{-\delta \cdot t} \leq t \cdot \delta \cdot \log M\)。 #### 6. 不可区分性定理 - **定理内容**：考虑 2 - BRO 模型中的异或组合器 \(C_{H_1,H_2}^{\oplus}(x) := H_1(x) \oplus H_2(x)\)，对于任何 \(\overline{p} := (p_1, \ldots, p_{c + 1}) \in N^{c + 1}\)，\(0 < \gamma < 1\) 和整数 \(c \geq 0\)，存在模拟器 \(Sim[\overline{p}, \gamma] := (Sim_{H_1}^{RO}, Sim_{H_2}^{RO}, Sim_{BD_1}^{RO}[\overline{p}, \gamma], Sim_{BD_2}^{RO}[\overline{p}, \gamma])\)，使得任何区分器 \(D\) 在切换到另一个后门预言机之前总是对一个后门预言机进行 \(Q\) 次查询（从 \(Bd_1\) 开始并总是接收 \(\ell\) 位响应），总切换次数为 \(c\)，同时允许任意交错最多 \(q_H\) 次原始查询和 \(q_C\) 次构造查询，有： \[ Adv_{C_{H_1,H_2}^{\oplus},Sim[\overline{p},\gamma]}(D) \leq (c + 1) \cdot \gamma + \log M \cdot \