仿射行列式程序候选混淆器的密码分析

### 仿射行列式程序候选混淆器的密码分析 #### 1. 基础攻击原理 对于大多数仿射行列式程序（ADP），一个特定方程的结果通常为 0 或 2，且两者出现的概率均为 1/2。通过计算 $\sum_{x\in\{0,1\}^2} \det(L''(x)) \bmod 4$，我们至少有 3/4 的概率猜出 ADP 的随机选择。当结果为 0 时，我们猜测为情况 1；否则，猜测为情况 2。 #### 2. 高级情况分析 在基础情况中，我们展示了两个矩阵为 0 的 ADP 可以与在相同输入位上具有非零矩阵的功能等效 ADP 区分开来。然而，这种条件较为受限，例如可以通过在每个矩阵的对角线上添加一个非零虚拟项来避免。因此，我们提出问题：能否在不强制 $B_1 = B_2 = 0$ 的情况下应用攻击？答案是肯定的。 基础情况攻击的关键在于，当不同输入下的 $2e_{j,k}^{(i)} \det(L'(x)_{(j,k)})$ 项相等时，我们可以将它们组合起来。具体而言，对于任意 $x_1, x_2 \in \{0, 1\}^2$，有 $\hat{L}'(x_1) = \hat{L}'(x_2)$，其中 $\hat{M}$ 是 $M_{\ell\times\ell}$ 的子式矩阵，即： \[ \hat{M} = \begin{bmatrix} \det(M_{(1,1)}) & \det(M_{(1,2)}) & \cdots & \det(M_{(1,\ell)}) \\ \det(M_{(2,1)}) & \det(M_{(2,2)}) & \cdots & \det(M_{(2,\ell)}) \\ \vdots & \vdots & \ddots & \vdots \\ \det(M_{(\ell,1)}) & \det(M_{(\ell,2)}) & \cdots & \det(M_{(\ell,\ell)}) \end{bmatrix} \] 在基础情况中，我们假设 $L'(x_i)$（$i = 1, 2, 3, 4$）的整个矩阵彼此相等。但实际上，攻击生效只需要 $\hat{L}'(x_i)$（$i = 1, 2, 3, 4$）彼此相等。接下来，我们分析 $\hat{L}'(x)$ 和 $\hat{L}(x)$ 之间的关系，以确定在对 $L(x)$ 应用随机线性变换（RLS）后，$\hat{L}'(x)$ 的元素在多大程度上是不可预测的。 ##### 2.1 顶点分类 $L'(x)$ 中的顶点可分为两类：原始顶点和中间顶点。$\hat{L}'(x)$ 的元素有以下几种情况： 1. 对于所有满足 $s \leq \ell$ 且 $j > 1$ 的 $s, j \in [\ell + 1]$，有 $\hat{L}'(x)[v_s, v_j] = \hat{L}(x)[v_s, v_j]$。 2. 对于所有满足 $s \leq \ell$ 且 $i < j$ 的 $s, i, j \in [\ell + 1]$，有 $\hat{L}'(x)[v_s, v_{i,j}] = \hat{L}(x)[v_s, v_j] \cdot L'(x)[v_{i,j}, v_j]$。 3. 对于所有满足 $s < t$ 且 $j > 1$ 的 $s, t, j \in [\ell + 1]$，有 $\hat{L}'(x)[v_{s,t}, v_j] = \hat{L}(x)[v_s, v_j] \cdot L'(x)[v_s, v_{s,t}]$。 4. 对于所有满足 $s < t$ 且 $i < j$ 的 $s, t, i, j \in [\ell + 1]$，有 $\hat{L}'(x)[v_{s,t}, v_{i,j}](v_{s,t} \neq v_{i,j}) = \hat{L}(x)[v_s, v_j] \cdot L'(x)[v_{i,j}, v_j] \cdot L'(x)[v_s, v_{s,t}]$。 5. 对于所有满足 $i < j$ 的 $i, j \in [\ell + 1]$，有： \[ \hat{L}'(x)[v_{i,j}, v_{i,j}] = \begin{cases} \det(L(x)), & L(x)[v_i, v_j] = 0 \text{ 或 } L'(x)[v_i, v_j] = 1 \\ \det(L(x)_{(v_i,v_j)=0}), & L(x)[v_i, v_j] = 1 \text{ 且 } L'(x)[v_i, v_j] = 0 \end{cases} \] ##### 2.2 定理证明 上述定理通过以下四个引理证明： - **引理 2**：对于所有满足 $s \leq \ell$ 且 $j > 1$ 的 $s, j \in [\ell + 1]$，有 $\hat{L}'(x)[v_s, v_j] = \hat{L}(x)[v_s, v_j]$。比较 $L'(x)_{(v_s,v_j)}$ 和 $L(x)_{(v_s,v_j)}$，主要有两种差异：一是 $L'(x)_{(v_s,v_j)}$ 有对应中间顶点的行和列；二是 $L'(x)_{(v_s,v_j)}[v_i, v_t]$ 可能不等于 $L(x)_{(v_s,v_j)}[v_i, v_t]$。通过删除中间顶点及相关边，并同时恢复原始顶点之间的值，可将 $L'(x)_{(v_s,v_j)}$ 转换为 $L(x)_{(v_s,v_j)}$，且转换过程中行列式不变。 - **引理 3**：对于所有满足 $i < j$ 的 $i, j \in [\ell + 1]$，有 $\hat{L}'(x)[v^*, v_{i,j}] = \hat{L}(x)[v^*, v_j] \cdot L'(x)[v_{i,j}, v_j]$，其中 $v^*$ 是原始顶点或中间顶点，且 $v^* \neq v_{i,j}$ 且 $v^* \neq v_1$。 - **引理 4**：对于所有满足 $s < t$ 的 $s, t \in [\ell + 1]$，有 $\hat{L}'(x)[v_{s,t}, v^*] = \hat{L}(x)[v_s, v^*] \cdot L'(x)[v_s, v_{s,t}]$，其中 $v^*$ 是原始顶点或中间顶点，且 $v^* \neq v_{s,t}$ 且 $v^* \neq v_{\ell + 1}$。 - **引理 5**：对于所有满足 $i < j$ 的 $i, j \in [\ell + 1]$，有 $\hat{L}'(x)[v_{i,j}, v_{i,j}] = \det(L(x)_{(v_i,v_j)=L'(x)[v_i,v_j]})$。 ##### 2.3 必要充分条件 根据定理 3，我们可以找到 $\hat{L}'(x_1) = \hat{L}'(x_2)$ 的必要充分条件，即定理 4：对于满足以下条件的 $L(x_1)$ 和 $L(x_2)$，无论 RLS 注入的随机性如何，都有 $\hat{L}'(x_1) = \hat{L}'(x_2)$： 1. $\hat{L}(x_1) = \hat{L}(x_2)$。 2. 对于所有满足 $i \leq \ell$ 且 $j > 1$ 且 $L(x_1)[v_i, v_j] \neq L(x_2)[v_i, v_j]$ 的 $i, j \in [\ell + 1]$，$\hat{L}(x_1)$ 的第 $i$ 行和第 $j$ 列的元素均为 0。 3. 对于所有满足 $i < j$ 的 $i, j \in [\ell + 1]$，有 $\det(L(x_1)_{(v_i,v_j)=0}) = \det(L(x_1)) = \det(L(x_2)) = \det(L(x_2)_{(v_i,v_j)=0})$。 #