子集和问题的新时间-内存权衡及在二进制线性码解码中的应用

### 子集和问题的新时间 - 内存权衡及在二进制线性码解码中的应用 #### 1. BCJ算法及改进 BCJ算法最终选择 $\ell_1 = r_1$ 和 $\ell_2 = r_2 - r_1$，从而得到 $\ell_3 = r_3 - r_2$。对 $\alpha_i$ 进行数值优化后，BCJ 配置的时间复杂度为 $2^{0.291n}$。Bonnetain 等人展示了更灵活地选择 $\ell_1$ 和 $\ell_2$ 以及相应调整 $\ell_3$ 可将时间复杂度降至 $2^{0.289n}$。进一步将 $D_i$ 的数字集扩展到 $\{0, \pm1, 2\}$，可将时间复杂度降至 $2^{0.283n}$，这是随机子集和问题已知的最佳时间复杂度。 BCJ 算法在搜索树深度为 4 时达到最优时间复杂度，但一般来说，最优深度随应用而异。 #### 2. 新的子集和权衡策略 广义 BCJ 算法本身具有一定的时间 - 内存权衡潜力。可以通过优化 $\ell_i$ 的选择来平衡内存使用，因为 $\ell_i$ 越大，列表大小越小。但 $\ell_i$ 的总体大小受限于最后一个列表应包含解的表示这一限制。 新的权衡策略通过放宽这一限制，即不要求最后一个列表包含解，从而更友好地平衡列表的内存使用。然后通过多次随机执行算法来确保最终找到解。 主要的运行时优势在于可以在后续随机执行中重用树的部分内容，降低每次迭代的成本。此外，使用 Dissection 框架构建一级列表也带来了改进。 当改变树中的一些位约束时，并非所有级别都会受到影响，因此只需重新计算依赖于这些更改约束的列表。通过适当调整参数并利用过滤机制，可以保证频繁重建列表的成本远低于重建整个树的成本。 对于较高的内存参数 $M \geq 2^{0.169n}$，这种部分重建策略结合放宽正确性约束可以带来显著的改进。当内存达到一定程度时，基础列表开始主导内存使用。为了减小这些列表的大小，算法可以选择在一级使用较小的集合 $D_1$。对于 BCJ 算法，这意味着减少 -1 项的数量，直到枚举中最终不包含 -1 项。此时，基础列表需要的内存约为 $2^{0.169n}$，列表大小达到最小。 为了解决这个问题，采用 7 - Dissection 算法替代中间相遇策略来对一级域进行详尽检查。7 - Dissection 算法不仅可以为 $M < 2^{0.169n}$ 的内存参数提供实例，还能在 $M \geq 2^{0.169n}$ 的高内存区域带来轻微的时间改进，因为优化可以选择更优、通常更大的集合 $D_1$ 而不超过内存限制。 #### 3. BCJ 算法的适应 设 $T$ 为完整树，$T_i$（$i = 1, 2, 3$）为仅包含从第 $i$ 级开始的列表的子树。用 $2^{t_i}$ 表示从先前级别的已存在列表重建子树 $T_i$ 的次数。 - 首先，仅更改模约束 $c_{z1}$ 的上 $\ell_3$ 位，这只需要重新计算子树 $T_3$，因为 $i \leq 2$ 的 $i$ 级列表不依赖于这些位。由于这些位只有 $2^{\ell_3}$ 种选择，所以 $t_3 \leq \ell_3$。 - 如果 $2^{\ell_3}$ 次迭代不足以找到解，则开始修改模约束 $c_{y1}$、$c_{y2}$、$c_{z1} \bmod 2^{\ell_2}$ 的上 $\ell_2$ 位。这意味着 $t_2 \leq 3\ell_2$。对于这些位的每个不同选择，还需要为上 $\ell_3$ 位的不同选择重新计算子树 $T_3$ $2^{t_3}$ 次。 - 如果 $2^{3\ell_2 + \ell_3}$ 次迭代仍然不足以找到解，则最终开始修改所选模约束的下 $\ell_1$ 位。对于每个低位选择，需要多次重建树 $T_2$ 和 $T_3$。由于有七个可以自由选择的约束，所以 $t_1 \leq 7\ell_1$。 最后，使用 7 - Dissection 算法计算一级列表，而不是中间相遇算法。 以下是修改后的 BCJ 权衡算法的伪代码： ```plaintext Algorithm 2: BCJ Trade-Off Input: a ∈ (Z_{2^n})^n, t ∈ Z_{2^n} Output: e ∈ {0, 1}^n with ⟨a, e⟩ = t mod 2^n 1. Choose optimal ℓ1, ℓ2, ℓ3 and Di, i = 1, 2, 3, let r := r3 + 2r2 + 4r1 2. repeat 2^t1 := 2^max(7ℓ1−r,0) times 3. Choose random cz1 ∈ F_ℓ^2, cy1, cy3 ∈ F_{ℓ1+ℓ2}^2, cx1, cx3, cx5, cx7 ∈ F_ℓ1^2 4. Set remaining constraints according to Eq. (2) 5. Compute L^{(1)}_i = {xi | ⟨a, xi⟩ = cxi mod 2^ℓ1, xi ∈ D1, }, via 7-Dissection, i = 1, ..., 8 6. repeat 2^t2 := 2^max(7ℓ1+3ℓ2−r,0)−t1 times 7. Choose randomly the upper ℓ2 bits of cz1, cy1, cy3 mod 2^ℓ1+ℓ2 8. Update cz2, cy2, cy4 according to Eq. (2) 9. Compute L^{(2)}_i = {yi | ⟨a, yi⟩ = cyi mod 2^ℓ1+ℓ2, yi ∈ D2, yi = x2i−1 + x2i}, from L^{(1)}_{2i−1}, L^{(1)}_{2i}, i = 1, ..., 4 10. repeat 2^t3 := 2^max(7ℓ1+3ℓ2+ℓ3−r,0)−t1−t2 times 11. Choose randomly the upper ℓ3 bits of cz1 12. Update cz2 according to Eq. (2) 13. Compute L^{(3)}_i = {zi | ⟨a, zi⟩ = czi mod 2^ℓ, zi ∈ D3, zi = y2i−1 + y2i}, from L^{(2)}_{2i−1}, L^{(2)}_{2i}, i = 1, 2 L = {e | ⟨a, e⟩ = t mod 2^n, e ∈ D4, e = z2i−1 + z2i}, from L^{(3)}_1, L^{(3)}_2 if |L| > 0 then 14. return e ∈ L ``` #### 4. 复杂度分析 - **内存复杂度**：内存复杂度与之前类似，唯一的区别是基础列表的内存需求现在由 7 - Dissection 算法的内存需求 $M_{7D}$ 替代，即 $M = \max(M_