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

### 规则综合征解码问题的新代数方法 在代数密码分析领域，规则综合征解码（RSD）问题是一个重要的研究方向。本文将介绍一种新的代数方法来解决RSD问题，包括代数建模、希尔伯特系列的推导、见证度的估计以及混合方法的应用。 #### 1. 代数建模 为了解决RSD问题，我们引入了两种多项式系统建模方法： - **建模1（大域上）**：对于给定的RSD实例 $(H, s^T)$ 在任意（大）域 $F$ 上，建模1是多项式序列 $F := P ∪ B$，其中： - $P$ 是由奇偶校验方程 $s^T = He^T$ 给出的 $n - k$ 个线性多项式的集合。 - $B$ 是描述误差向量 $e$ 规则形式的二次多项式集合，即对于 $1 ≤ i ≤ h$ 和 $1 ≤ j_1 < j_2 ≤ β$，有 $e_{i,j_1}e_{i,j_2} = 0$。 此外，还包括域方程 $e_{i,j}^{|F|} - e_{i,j} = 0$，以使建模1生成的理想是零维的。不过，由于这些方程的次数较高，在计算中用处不大。建模1仅表明每个块中的汉明重量最多为1，因为我们对非零坐标没有信息。 - **建模2（$F_2$ 上）**：对于给定的二进制RSD实例 $(H, s^T)$，建模2是多项式序列 $F_{F_2} = P ∪ B ∪ Q_{F_2} ∪ L_{F_2}$，其中 $P$ 和 $B$ 与建模1相同，并且： - $Q_{F_2}$ 是域方程 $e_{i,j}^2 - e_{i,j} = 0$ 对于 $1 ≤ i ≤ h$ 和 $1 ≤ j ≤ β$ 的集合。 - $L_{F_2}$ 是 $h$ 个线性方程 $1 - \sum_{j = 1}^{\beta} e_{i,j} = 0$ 对于 $1 ≤ i ≤ h$ 的集合，它表示每个块有唯一的非零坐标。 在这两种情况下，主要贡献是包含 $n - k = n(1 - R)$ 个奇偶校验方程的集合 $P$。因此，这种方法对于非恒定速率的实例是相关的。从公共生成矩阵 $G$ 可以构造等效的对偶LPN实例，然后对这个对偶问题使用建模1或2。未知数仅仅是误差向量 $e$ 的坐标，对于感兴趣的参数范围，我们期望解的数量与初始RSD实例相同，即1。 下面是两种建模方法的对比表格： | 建模方法 | 适用域 | 多项式集合 | 特点 | | ---- | ---- | ---- | ---- | | 建模1 | 任意大域 $F$ | $F := P ∪ B$ | 仅表明每个块汉明重量最多为1，域方程计算用处不大 | | 建模2 | $F_2$ | $F_{F_2} = P ∪ B ∪ Q_{F_2} ∪ L_{F_2}$ | 明确每个块有唯一非零坐标 | #### 2. 推导希尔伯特系列 我们的目标是计算与建模1和建模2分别关联的齐次理想 $I := ⟨F^{(h)}⟩$ 和 $I_{F_2} := ⟨F_{F_2}^{(h)}⟩$ 的希尔伯特系列。 ##### 2.1 建模1的希尔伯特系列 回顾建模1是序列 $F = P ∪ B$，第一步是通过单项式计数计算 $S := A/⟨B^{(h)}⟩$ 的希尔伯特系列 $HS(z)$。由于 $S$ 不是多项式环，我们引入以下假设： - **假设1**：考虑建模1的一个实例 $F$，设 $d_{reg}$ 是 $I := ⟨F^{(h)}⟩$ 的正则度。定义商环 $S := A/⟨B^{(h)}⟩$，并设 $P^{(h)} = \{p_1^{(h)},..., p_{n - k}^{(h)}\}$ 表示线性奇偶校验方程的集合。我们假设对于 $1 ≤ i ≤ n - k$，在 $S/⟨p_1,..., p_{i - 1}⟩$ 中 $g_ip_i = 0$ 且 $\text{deg}(g_ip_i) < d_{reg}$ 意味着 $g_i = 0$ 在 $S/⟨p_1,..., p_{i - 1}⟩$ 中。 在这个假设下，建模1关联的齐次理想 $I$ 的希尔伯特系列为： $H_{A/I}(z) = [(1 - z)^{n - k} \cdot (1 + \beta \cdot \frac{z}{1 - z})^h]_+$ 其中 $[.]_+$ 表示在第一个非正系数后截断，$(1 - z)^{n - k} \cdot (1 + \beta \cdot \frac{z}{1 - z})^h$ 称为 $I$ 的生成系列。 ##### 2.2 建模2的希尔伯特系列 建模2包含额外的结构方程，添加最后一组方程 $L_{F_2}$ 时会出现困难，因为它会产生另一种类型的消去。为了保持与建模1相同的分析类型，我们使用 $L_{F_2}$ 移除 $h$ 个变量。定义一个分级环同态 $L$： $L : F_2[e] \to F_2[x]$ $e_{i,j} \to x_{i,j}$，对于 $1 ≤ i ≤ h$ 和 $1 ≤ j < \beta$ $e_{i,\beta} \to \sum_{j = 1}^{\beta - 1} x_{i,j}$，对于 $1 ≤ i ≤ h$ 然后定义 $A' := L(A)$，$I' := L(I^{(h)})$，$B' := L(B^{(h