规则综合征解码问题的新代数方法

### 规则综合征解码问题的新代数方法 #### 1. 背景与基础概念 在研究规则综合征解码问题时，一些关键概念和量的估计十分重要。首先，$[z^j] (H(z))$ 表示级数 $H$ 中单项式 $z^j$ 的系数。同时，需要估计 $n_{\mu}$，它是Macaulay矩阵一行中非零项的数量，这与初始奇偶校验方程的单项式内容直接相关。假设矩阵 $H$ 为系统形式，那么 $n_{\mu} \leq k + 1 = O(k)$。对于专门化系统，可固定误差的 $f$ 个底部块，得到更好的因子 $n_{\mu,(f,u)} \leq k + 1 - f \cdot u$，这可能在最终复杂度上节省一些比特。 #### 2. 混合方法的时间复杂度 在假设3以及特定假设条件下，建模1的混合方法在 $F$ 运算中的时间复杂度可估计为： \[ O\left(\min_{0\leq f\leq h, 0\leq u\leq \beta} \left\{P^{-1}_{(f,u)} \cdot 3 \cdot n_{\mu,(f,u)} \cdot \left(M_{(f,u) \leq dwit_{(f,u)}}\right)^2\right\}\right) \] 其中： - $P_{(f,u)} := (1 - u/\beta)^f$ - $n_{\mu,(f,u)} := k + 1 - f \cdot u$ - $M_{(f,u) \leq dwit_{(f,u)}}$ 在方程(11)中定义 - $dwit_{(f,u)}$ 是方程(10)中生成级数的第一个非正系数的索引 对于建模2也有类似的结论。不过，在第4.1和4.2节中提出的变量固定方法可能是最朴素的，尽管利用规则结构能带来较高的成功概率，但其他方法可能能更快降低求解次数。 #### 3. 假设的合理性与实验验证 所使用的假设与代数密码分析中常见的假设非常相似。具体而言，这些一般性假设涉及奇偶校验方程的线性部分，而这些多项式仅依赖于矩阵 $H$。尽管底层代码 $C$ 在原始表述中通常是 $d$ - 局部的，但从公共矩阵 $G$ 得到的奇偶校验矩阵在某种意义上并无特殊之处。否则，这种特殊性质可能会被攻击利用，或者表明该实例比标准LPN更弱。 在类似的情境中，用于求解LWE的Arora - Gˆe系统通常被假设为半规则的，相关实验也验证了其求解次数与相同规模的随机系统一致。我们对第3和第4节中的假设进行了实验测试，包括假设1、2及其混合对应情况，以及建模1和2的混合 $dwit$ 估计和建模1的普通 $dwit$ 估计。实验结果表明，假设1和2在所有实验中都是正确的，仅在建模2的少数混合情况下观察到差异，而见证次数的估计在所有测试案例中都是正确的。 #### 4. 应用于特定参数 我们使用第4.2节的混合技术估计了对一些非恒定速率的LPN参数集的攻击复杂度。对于每个参数集，使用命题5计算建模1的最优复杂度（建模2使用附录B.2中的命题7）。报告了导致最佳复杂度的 $(f, u)$ 对以及相关的见证次数估计 $d_{conj} := dwit_{(f,u)}$。当 $f$ 和 $u$ 为正时，使用第4.3节的上界估计 $dwit_{(f,u)}$；当 $f = u = 0$ 时，使用方程(6)的估计。稀疏因子在大域上为 $k + 1 - f \cdot u$，在 $F_2$ 上为 $\min (k + 1 - f \cdot u, k/2 + 1)$，Wiedemann算法的常数取为3。 我们考虑的参数最初由相关文献提出，其在 $F_2$ 和 $F_{2^{128}}$ 上的安全性已被重新评估。具体参数如下表所示： **表1：在 $F_2$ 上的混合方法（建模2）** | $n$ | $k$ | $h$ | 最佳攻击 [34] | $d_{conj}$ 普通 | $(f, u)$ | $d_{conj}$ XL混合 | | --- | --- | --- | --- | --- | --- | --- | | 222 | 64770 | 2735 | 104 | 2 | (0, 0) | 2 | 103 | | 220 | 32771 | 1419 | 99 | 3 | (1159, 2) | 2 | 98 | | 218 | 15336 | 760 | 95 | 3 | (657, 7) | 2 | 104 | | 216 | 7391 | 389 | 91 | 4 | (373, 10) | 2 | 108 | | 214 | 3482 | 198 | 86 | 6 | (197, 11) | 2 | 106 | | 212 | 1589 | 98 | 83 | 8 | (88, 13) | 2 | 103 | | 210 | 652 | 57 | 94 | 12 | (54, 9) | 2 | 101 | **表2：在 $F_{2^{128}}$ 上的混合方法（建模1）** | $n$ | $k$ | $h$ | 最佳攻击 [34] | $d_{conj}$ 普通 | $(f, u)$ | $d_{conj}$ XL混合 | | --- | --- | --- | --- | --- | --- | --- | | 222 | 64770 | 2735 | 108 | 2 | (0, 0) | 2 | 104 | | 220 | 32771 | 1419 | 107 | 3 | (1246, 3) | 2 | 102 | | 218 | 15336 | 760 | 105 | 3 | (670, 8) | 2 | 107 | | 216 | 7391 | 389 | 103 | 4 | (374, 11) | 2 | 111 | | 214 | 3482 | 198 | 101 | 6 | (197, 12) | 2 | 110 | | 212 | 1589 | 98 | 100 | 8 | (96, 13) | 2 | 107 | | 210 | 652 | 57 | 111 | 14 | (55, 10) | 2 | 111 | #### 5. 结果分析 总体而言，攻击复杂度与最佳攻击相当接近，尽管在表1和表2的大多数实例中略高于最佳值。混合方法可以看作是Prange算法的类似物，它绕过了普通系统的高见证次数。由于我们的攻击不是纯粹的代数攻击，因此不应期望复杂度之间存在很大差距。而且，与小尺度参数（表1和表2）相比，大尺度参数（表4和表5）中的复杂度差异明显减小。 此外，当能在次数2、3下求解且无需固定大量变量时，代数攻击比ISD算法更高效，这可能暗示了一个前ISD算法未涵盖的参数薄弱区域。同时，代数攻击在大域上与已知技术相比表现更好，这可能是因为当域大小 $|F| \to +\inf