最小化Even-Mansour密码以实现顺序不可区分性

# 最小化Even - Mansour密码以实现顺序不可区分性 ## 1. 相关概念介绍 ### 1.1 相关性难解性 相关性难解性用于描述在函数集合的输入和输出之间寻找可利用关系的难度。考虑一个关于二进制序列对的关系 $R$： - 若对于理想密码 $E$，不存在高效的预言机图灵机 $M_E$ 能以显著的成功概率输出一个 $m$ 元组 $(x_1, \ldots, x_m)$，使得 $((x_1, \ldots, x_m), (E(x_1), \ldots, E(x_m))) \in R$，则称 $R$ 相对于 $E$ 是规避的。 - 若对于理想分组密码 $EMP$，不存在高效的预言机图灵机 $M_P$ 能以显著的成功概率输出一个 $m$ 元组 $(x_1, \ldots, x_m)$，使得 $((x_1, \ldots, x_m), (EMP(x_1), \ldots, EMP(x_m))) \in R$，则称 $EMP$ 相对于 $R$ 是相关性难解的。 如果 $EMP$ 与 $E$ 是顺序不可区分的，那么对于任何相对于 $E$ 是规避的 $m$ 元关系 $R$，$EMP$ 相对于 $R$ 是相关性难解的。 ### 1.2 单密钥单置换EMSP的滑动攻击 $t$ 轮的 $EMSP_{p}^t$ 在每一轮都使用相同的置换 $p$，其定义为： $EMSP_{p}^t(k, u) := k \oplus p(\ldots k \oplus p(k \oplus p(k \oplus p(k \oplus u)))\ldots)$ 攻击步骤如下： 1. 任意选取 $x \in \{0, 1\}^n$，查询 $p(x) \to y$。 2. 计算 $k \leftarrow x \oplus y$。当且仅当 $E(k, y) = x$ 时输出 1。 在与 $(EMSP_{p}^t, p)$ 交互时，无论轮数 $t$ 为多少，该攻击总是输出 1。在理想世界中，模拟器需要找到一个三元组 $(x \oplus y, y, x) \in (\{0, 1\}^n)^3$，使得理想密码 $E(x \oplus y, y) = x$。当模拟器进行 $q_S$ 次查询时，前向理想密码查询 $E(x \oplus y, y)$ 响应为 $x$ 的概率至多为 $1/(2^n - q_S)$；反向查询 $E^{-1}(x \oplus y, y)$ 响应为 $x$ 的概率至多为 $1/(2^n - q_S)$。因此，模拟器确定 $E(x \oplus y, y) = x$ 的概率至多为 $q_S/(2^n - q_S)$，攻击优势至少为 $1 - q_S/(2^n - q_S)$。 ## 2. 4轮EM2P4的顺序不可区分性 ### 2.1 定理描述 假设 $p_1$ 和 $p_2$ 是两个独立的随机置换，4轮单密钥Even - Mansour方案 $EM2P_{p_1,p_2}^4$ 定义为： $EM2P_{p_1,p_2}^4(k, u) := k \oplus p_1(k \oplus p_2(k \oplus p_2(k \oplus p_1(k \oplus u))))$ 该方案与理想密码 $E$ 是强统计意义下的 $(q, \sigma, t, \varepsilon)$ - 顺序不可区分的，其中 $\sigma = q^2$，$t = O(q^2)$，且 $\varepsilon \leq \frac{20q^3 + 29q^4}{2^n} = O(\frac{q^4}{2^n})$（假设 $q + 2q^2 \leq 2^n/2$）。 ### 2.2 模拟器设计 #### 2.2.1 随机性和接口 模拟器 $S$ 为区分器提供四个接口 $P_1$、$P_1^{-1}$、$P_2$ 和 $P_2^{-1}$，用于查询内部置换，查询输入可以是集合 $\{0, 1\}^n$ 中的任意元素。为了方便描述模拟过程中的惰性采样，使用两个随机置换 $p_1$ 和 $p_2$ 来明确模拟器使用的随机性。 #### 2.2.2 维护查询记录 模拟器 $S$ 内部维护两个集合 $\Pi_1$ 和 $\Pi_2$，其元素形式为 $(i, x, y) \in \{1, 2\} \times \{0, 1\}^n \times \{0, 1\}^n$。对于任意 $x \in \{0, 1\}^n$ 和 $i \in \{1, 2\}$，最多存在一个 $y \in \{0, 1\}^n$ 使得 $(i, x, y) \in \Pi_i$，反之亦然。如果无法保证这种一致性，模拟器将终止。这两个集合定义了两个部分置换，用 $domain(\Pi_i)$ 和 $range(\Pi_i)$ 分别表示满足 $\exists z \in \{0, 1\}^n$ 使得 $(i, x, z) \in \Pi_i$ 和 $(i, z, y) \in \Pi_i$ 的所有 $n$ 位值 $x$ 和 $y$ 的集合，用 $\Pi_i(x)$ 和 $\Pi_i^{-1}(y)$ 表示对应的 $z$ 值。 #### 2.2.3 模拟策略 当区分器 $D$ 查询 $P_i(x)$ 或 $P_i^{-1}(y)$ 时： - 如果 $x \in \Pi_1$ 或 $y \in \Pi_1^{-1}$，则直接用 $\Pi_1(x)$ 或 $\Pi_1^{-1}(y)$ 响应。 - 否则，查询 $p_i$ 得到 $y \leftarrow p_i(x)$ 或 $x \leftarrow p_i^{-1}(y)$。如果 $y \notin range(\Pi_i)$，则将记录 $(i, x, y)$ 添加到集合 $\Pi_i$ 中；否则，为避免 $\Pi_i$ 中的不一致性，模拟器终止。 - 当 $i = 1$ 时，直接返回 $x$ 或 $y$；当 $i = 2$ 时，完成由新记录 $(2, x, y)$ 和 $\Pi_2$ 中先前创建的记录形成的部分链。 具体来说，当新的对抗性查询是 $P_2(x)$ 且 $S$ 向 $\Pi_2$ 添加新记录 $(2, x, y)$ 时： - 对于每一对 $\left((2, x, y), (2, x', y')\right) \in (\Pi_2)^2$，计算 $k \leftarrow y \oplus x'$ 和 $x_4 \leftarrow y' \oplus k$。内部调用 $P_1$ 得到 $y_4 \leftarrow P_1(x_4)$ 和 $v \leftarrow y_4 \oplus k$。查询理想密码得到 $u \leftarrow E^{-1}(k, v)$，进一步计算 $x_1 \leftarrow u \oplus k$ 和 $y_1 \leftarrow x \oplus k$。如果 $x_1 \notin domain(\Pi_1)$ 且 $y_1 \notin range(\Pi_1)$，则将记录 $(i, x, y)$ 添加到集合 $\Pi_i$ 中，以完成 4 - 链 $\left((1, x_1, y_1), (2, x, y), (2, x', y'), (1, x_4, y_4)\right)$；否则，模拟器终止。这个过程在伪代码中实现为过程 $Complete -$。 - 对于每一对 $\left((2, x', y'), (2, x, y)\right) \in (\Pi_2)^2$，计算 $k \leftarrow y' \oplus x$，$y_1 \leftarrow x' \oplus k$，$x_1 \leftarrow P_1^{-1}(y_1)$，$u \leftarrow x_1 \oplus k$；$v \leftarrow E(k, u)$，$y_4 \leftarrow v \oplus k$ 和 $x_4 \leftarrow y \oplus k$。当 $x_4 \notin domain(\Pi_1)$ 且 $y_4 \notin range(\Pi_1)$ 时，将适应记录 $(1, x_4, y_4)$ 添加到 $\Pi_1$ 中，以完成 $\left((1, x_1, y_1), (2, x', y'), (2, x, y), (1, x_4, y_4)\right)$；否则，模拟器终止。这个过程在伪代码中实现为过程 $Complete +$。 当 $D$ 查询 $P_2^{-1}(y)$ 时，模拟器的操作与 $P_2(x)$ 对称。 以下是模拟器的伪代码： ```plaintext 1: Simulator S_E,P 2: Variables: Sets Π1, Π2, XDom, and XRng, all initially empty 3: public procedure P1(x) 4: if x ∉ domain(Π1) then 5: y ← p1(x) 6: if Π1^(-1)(y) ≠ ⊥ then abort 7: if y ∈ XRng then abort 8: Π1 ← Π1 ∪ {(1, x, y)} 9: return Π1(x) 10: public procedure P1^(-1)(y) 11: if y ∉ range(Π1) then 12: x ← p1^(-1)(y) 13: if Π1(x) ≠ ⊥ then abort 14: if x ∈ XDom then abort 15: Π1 ← Π1 ∪ {(1, x, y)} 16: return Π1^(-1)(y) 17: public procedure P2(x) 18: if x ∉ domain(Π2) then 19: y ← p2(x) 20: Π2 ← Π2 ∪ {(2, x, y)} 21: forall (2, x', y') ∈ Π2 do 22: // 3+ chain 23: k ← y' ⊕ x 24: if y ⊕ k ∈ domain(Π1) 25: then abort 26: XDom ← XDom ∪ {y ⊕ k} 27: ```