基于子格BKZ的格约化算法

# 基于子格BKZ的格约化算法 ## 1. 格与子格的性质 对于维度为 $n$（$n < 200$）的格 $L$ 及其维度为 $n/2$ 的子格 $L_1$，有启发式结论：$\log \det(L_1) = \frac{1}{2} \log \det(L) + \alpha$，其中 $\alpha < 1$。 高斯启发式（Gaussian Heuristic）有更精确的形式： $GH(L) = \frac{\Gamma(\frac{n}{2} + 1)^{\frac{1}{n}} \det(L)^{\frac{1}{n}}}{\sqrt{\pi}}$ 子格 $L_1$ 中最短向量的估计长度为 $GH_1 = \frac{\Gamma(\frac{n}{4} + 1)^{\frac{2}{n}} \det(L_1)^{\frac{2}{n}}}{\sqrt{\pi}}$，且接近全格 $L$ 的最短长度。通过近似计算 $\det (L_1) \approx \sqrt{\det (L)}$，结合伽马函数的近似 $\Gamma(x) \sim \sqrt{2\pi}e^{-x}x^{x - \frac{1}{2}}$，可以得到： $\Gamma(\frac{n}{2} + 1)^{\frac{1}{n}} \approx \sqrt{2\pi}e^{-(\frac{1}{2} + \frac{1}{n})} (\frac{n}{2} + 1)^{\frac{1}{2} + \frac{1}{2n}}$ $\Gamma(\frac{n}{4} + 1)^{\frac{2}{n}} \approx \sqrt{2\pi}e^{-(\frac{1}{2} + \frac{2}{n})} (\frac{n}{4} + 1)^{\frac{1}{2} + \frac{1}{n}}$ 进而有： $\frac{\Gamma(\frac{n}{2} + 1)^{\frac{1}{n}}}{\Gamma(\frac{n}{4} + 1)^{\frac{2}{n}}} \approx e^{\frac{1}{n}} \cdot \frac{2(n + 2)}{n + 4} \cdot (\frac{n}{2} + 1)^{\frac{1}{2} + \frac{1}{n}}$ 结果表明，子格的估计最短长度 $gh_1$ 约为 $gh$ 的 $\sqrt{2}$ 倍，即： $\frac{GH_1}{GH} \approx \sqrt{2} \cdot \frac{\det(L_1)^{\frac{1}{n}}}{\det(L)^{\frac{1}{n}}} = \sqrt{2}$ 格基的实际性质也受格基约化程度的影响。并非所有向量都遵循几何级数假设，实际的高斯启发式值可能与估计值不同。通过对格和子格进行LLL或BKZ预处理后比较它们的高斯启发式值，发现与LLL约化的子格基相比，BKZ约化的子格的高斯启发式值明显更小，接近全格的高斯启发式值，而LLL约化的子格的高斯启发式值相对难以预测。进一步实验表明，块大小越大，子格的高斯启发式值越小，越接近全格的原始高斯启发式值。 ## 2. 子格上的基约化 基于上述子格性质的发现，我们尝试在子格上进行基约化。假设子格维度为全格的一半。对于BKZ约化的基（维度 $\leq 130$），子格 $L_1$ 的高斯启发式满足 $\lambda_1(L_1) \leq 1.41\lambda_1(L)$，且在维度达到100时，BKZ约化的基能提供比 $L$ 长约1.15倍的向量。因此，我们期望在子格中找到不比 $\lambda_1(L)$ 长太多的向量。 BKZ和其他基于枚举的约化算法常用于寻找短向量。约化效率通常受格的大小影响，在大多数情况下，算法生成约化基的时间成本较低。使用相同的块大小，BKZ在子格上恢复的向量的近似因子比在全格上更小。因此，我们探索这种约化调用是否能返回比全格中恢复的向量更短的向量。 为了进一步利用这一发现，还可以使用子格向量更新约化基。例如，当恢复的子格向量比前几个极小值中的一个更短时，可以将该向量插入全格基中，改变基向量的排列。通过这种方式对基添加一些扰动，并希望通过递归调用BKZ获得更好的约化基。 ## 3. m - SubBKZ约化算法 ### 3.1 基本算法 提出了子格BKZ约化的新算法，将一次BKZ遍历和一次子格最短向量问题（SVP）调用称为一轮。给定一个 $n$ 维的基 $B$（全格基），选择前 $n/2$ 个向量形成子格基 $B_1$。目标是为大基提供实用的约化算法，并使用FPYLLL库测试其性能。 算法1：SubBKZ ```plaintext 输入: 基 B, 子格块大小 b1, 全格块大小 b 输出: 约化后的基 B 设置列表 l = {}; 对 B 进行 BKZ 约化; 生成子格 L′; 对 L′ 进行 BKZ - b1 约化; 将约化后的 L′ 基向量添加到 l; 将列表 l 插入 B; 对 B 进行 BKZ - b 约化; ``` 在该算法过程中生成子格 $L′$，其基选自全格 $L$ 的前 $n/2$ 个基向量。假设子格 $L_1$ 维度为 $n/2$，SubBKZ和BKZ使用相同的块大小 $\beta$，则BKZ调用和子格约化的时间复杂度均为 $\beta^{\beta}/(2e)$。与BKZ输出长度约为 $(\beta^{\frac{1}{2\beta}})^n \cdot \det (L)^{\frac{1}{n}}$ 的向量相比，SubBKZ在子格上一轮约化得到的向量范数约为 $(\beta^{\frac{1}{2\beta}})^{\frac{n}{2}} \cdot \det (L_1)^{\frac{2}{n}} \approx (\beta^{\frac{1}{2\beta}})^{\frac{n}{2}} \cdot \det (L)^{\frac{1}{n}}$。因此，在相同时间复杂度下，SubBKZ能产生更短的向量，但实际的BKZ结果可能与理论不同。 ### 3.2 实用的SubBKZ变体 #### 递归短向量搜索 子格 $L_1$ 的估计行列式为： $\det (L_1) = \prod