6.2 难度阶梯：BKZ、枚举与筛法

6.2 难度阶梯：BKZ、枚举与筛法

攻击格难题的工具排成一条清晰的阶梯：枚举精确但超指数、筛法指数干净且可量子加速、BKZ 则是工程化的总装线——用 LLL 打底，分块调用前两者当"子程序"。本节把每一级的成本公式、内存代价与实战维数摆上桌面，并走通一条完整的 LWE 原始攻击流水线。

承接 6.1 节：LLL 快而不精，近似因子指数劣化。攻击者的对策不是换算法，而是给 LLL 加一个"精度旋钮"——本节拧这个旋钮，并把 3.3 节账本里的每个数字对应到具体的机器型号上。

第一级：枚举——精确但认维数

枚举的思路朴实：在格上按半径递增 systematically 搜索所有候选，保证找到真解。Fincke-Pohst 型枚举配合 Gram-Schmidt 剪枝后，代价仍是 2^{\Theta(\beta \log \beta)} 量级——比指数还多一个对数因子。维数 50 上下它好使，维数过百就吃力；但它有一个不可替代的优点：精确。工程上枚举常被当作小维数"预言机"使用——这正是下一级 BKZ 的接口。

第二级：筛法——指数干净的现代主力

筛法（sieve）用空间换时间：维护一个不断互减的短向量库，让最短向量在碰撞中浮出。当前最好实现（BDGL 一族）的账目是：

数字虽小有讲究：时间指数 0.292 是 2016 年的算法突破，此前是 0.318；内存指数 0.208 意味着 \beta = 400 时需要 2^{83} 比特存储——比全人类硬盘的总和还多出几十个数量级。筛法在百余维可实战（学术界已有维数 180 上下的筛法记录），到 400 维以上只能停在纸面上。量子版用 Grover 风格技巧把时间指数压到约 0.265，内存要求依旧——这条"量子折让约 8%"就是第 3 章量子安全位数的出处。

第三级：BKZ——把预言机装进流水线

BKZ（Block Korkine–Zolotarev）的机制一句话：把 n 维基切成滑动的 \beta 维窗口，每个窗口里调一次精确 SVP 预言机（小 \beta 用枚举、大 \beta 用筛法），把窗口内最短向量换进去，滑到头算一轮，循环到不再改进。块大小 \beta = 2 时它几乎就是 LLL；\beta 越大输出基越短、代价指数越高。工程上用根埃尔米特因子 \delta 描述输出质量：LLL 约 \delta \approx 1.021，BKZ-20 约 1.0128，BKZ-30 更小——\delta 每降千分之一，攻击可解的维数就上一个台阶。

攻击 LWE 的完整流水线（原始攻击）如今是标准四步：

1 构造: 把 LWE 实例按 Kannan 嵌入升维，得到攻击格 B嵌入
2 规约: 用 LLL 预处理，再跑 BKZ，块大小 beta 逐级试到成功
3 圆整: 对输出的好基跑 Babai 圆整，捞出短向量
4 翻译: 短向量即私钥 s 或等价信息，验证解密一致性
​

估算工具的内核就是这条流水线的数学模型：给定 (n, q, \sigma)，反推需要的 \beta，再代入筛法公式折算安全位数——第 3.3 节那些你亲手验算过的数字，全部产自这条流水线。看懂流水线还有一层实用价值：读到"某方案被 X 算法威胁"的消息时，先问该算法落在阶梯的哪一级、距离实用差几个数量级，多数标题在第一问之后就会自己安静下来。

阶梯总账与维数换安全的落点

图：攻击工具的成本阶梯

维数换安全的落点可以现场算一遍：Kyber512 的攻击格约 500 维、所需块大小约 490（3.3 节验过 143 位）；筛法到 490 维的时间是 2^{143}、内存 2^{102}——时间上理论可行、内存上物理不可实现，这正是"核心 SVP 口径"与"内存敏感口径"吵了多年的原因。你的三问清单（多少维、哪个梯级、是否出圈）在这里全部派上用场。

渐进 BKZ：工程师的调参手艺

实战跑 BKZ 不是一把拧到目标块大小，而是渐进策略：从 \beta = 20 起步，每轮加大几格，直到目标值或成功。好处有二：小 \beta 轮次把基整体熨平，大 \beta 轮次的成功率显著提高；且中途若成功（比如已捞出足够短的向量）即可提前收工。调参的三个旋钮——块大小序列、窗口内预言机选型（小 \beta 枚举、大 \beta 筛法）、每轮终止条件——构成了 lattice 攻击框架里最像"炼丹"的部分，但每一格旋钮背后都有质量指标（根埃尔米特因子）的反馈，并非玄学。你若复现攻击实验，记录这三个旋钮的取值轨迹，比只记最终 \beta 有用得多。

问题：量子加速为什么只有百分之八

直觉上的疑惑是 Grover 动辄平方根加速，这里怎么只有指数系数的折让。答案在筛法的结构里：筛法的主体是大量向量间的互减与库维护，其中能被 Grover 加速的"搜索型"子任务占比有限，加速主要体现在库内近邻查找（用 Grover 风格的量子走步把近邻搜索的指数从 0.292 的份额里挤出约 0.027）。这类结构性论证也提醒我们：量子加速的幅度取决于算法形态，不是任务名称——同一个"最短向量"问题，换一种算法形态，量子收益就完全不同。

留一道动手练习收束本章的攻击线：把 6.1 节的二维 LLL 代码改造成"渐进 BKZ 的玩具版"——外层循环让块大小从 2 逐轮加一，内层在每个二维窗口里跑一次枚举，输出每轮的根埃尔米特因子曲线。两个维数的玩具当然拉不开差距，但你会亲眼看到"块大小换质量"的曲线形态，而这条曲线放到四百维上，就是第 3 章账本里那行 0.292\beta 的出身。

要点速记：枚举精确但超指数，筛法 0.292beta 时间 0.208beta 内存，量子版 0.265beta；BKZ 用块大小买精度，根埃尔米特因子每降千分之一攻击上一个台阶；原始攻击四步流水线是估算工具的内核；攻击格维数与实战筛法记录之间的鸿沟，就是维数换安全的全部底气。

数学层的火力到此盘点完毕。下一节跳出纸面：量子计算机的真实边界，以及藏在计时器与功耗曲线里的暗箭。