3.3 安全强度估算：维度与模数的账本

3.3 安全强度估算：维度与模数的账本

安全强度估算把"难题很难"翻译成"需要约 2 的多少次方个基本操作"：先由攻击模型算出需要的 BKZ 块大小 \beta，再代入筛法复杂度公式折算成安全位数。本节把这本账的每一行公式、每一个换算系数摊开手算，并核对 Kyber 官方参数的落点——读完你就有了独立复核任何格密码参数表的能力。

前两节解决了"安全性由什么担保"；本节回答一个更工程的问题：担保值多少钱。这节是新添的动手节，因为参数估算是格密码工程师与密码分析者共享的日常工具——第 7 章参数表里的每个数字，都能用本节的公式现场验证。

账本第一行：攻击成本公式

当代对格难题最好的通用攻击是 BKZ 规约配合块内筛法（第 6 章细讲），成本由两个量决定：攻击格的维数 d 与所需的块大小 \beta。筛法在 \beta 维子空间里找最短向量的代价，按当前最好算法（BDGL 算法族）是：

量子版本用 Grover 技巧加速筛法，指数降到约 0.265\beta。这两个系数就是账本的核心汇率：块大小每涨 100，安全位数涨 29.2（经典）或 26.5（量子）。把汇率表直接算出来：

动手验两行：0.292 \times 438 = 127.9，正是 128 位；0.292 \times 877 = 256.1。整张表只有一行乘法，建议全表心算复核一遍——这本账没有任何黑箱。

账本第二行：块大小怎么定

\beta 不是拍脑袋来的：给定 LWE 实例的维数 n、模数 q、误差分布宽度，攻击者要用"逐块枚举或筛法"在嵌入格（3.2 节那座 Kannan 桥的产物）里挖出足够短的向量，所需的 \beta 随噪声相对宽度增大而增大。定性规律一句话：误差越宽、模数越小、维数越大，所需 \beta 越大，方案越安全。定量关系由估算工具计算——工作流是固定格式的：

输入: n=512, q=3329, 误差=居中二项分布 eta=3, 攻击=原始攻击
求解: BKZ 块大小 beta 使得 2^0.292beta 达到成功条件
输出: beta ≈ 490 -> 经典核心 SVP ≈ 2^143，量子 ≈ 2^119
​

上面正是 Kyber512（FIPS 203 的 ML-KEM-512）官方规格书的口径：经典核心 SVP 约 2^{143}、量子约 2^{119}，满足 NIST 类别一——对照 NIST 定的标尺"AES-128 密钥搜索的开销"（门数口径折合约 2^{143}）。同表 Kyber768（ML-KEM-768）经典约 2^{207} 达类别三，Kyber1024（ML-KEM-1024）经典约 2^{272} 达类别五。本节公式算出的 490 对应 143 位，与官方数字严丝合缝——这就是"能复核"的含义。

账本的三个脚注：估计为什么会有出入

不同工具、不同年份给出的安全位数不完全一致，原因通常落在三处。脚注一，成本口径：核心 SVP 方法论只数"筛法主循环步数"，隐含随机访问内存免费；门数模型（把内存访问也折成电路门）会给出更低的安全位数——对同一组参数，两种口径能差出十几个比特。脚注二，量子算法进展：2022 年 MATZOV 等工作改进了量子筛法的常数，把若干参数的量子估计削掉几个比特，NIST 为此专门公开讨论过参数是否需要上调；这也是标准定稿前最后一轮参数微调的直接动因。脚注三，系数本身会变：筛法指数 0.292 是 2016 年 BDGL 算法的纪录，若未来改进到 0.280，128 位安全所需 \beta 将从 438 涨到 457——参数设计必须给这类进展留出缓冲，所以你会在参数表里看到"安全边际"的说法。

把敏感性算成一笔具体的账：设某参数按 0.292 估算恰为 128 位。若攻击指数每十年进步 0.006（过去十年量级），四十年后汇率变 0.268，同样 \beta=438 只值 0.268 \times 438 = 117 位。这就是"密钥要能活几十年"的系统必须按悲观口径选参数的算术理由。

图：攻击成本阶梯——块大小换安全位数

动手工作流：给自己的参数做一次体检

把流程走成一个可重复的清单，四步。第一步，写实参：从方案规格书抄下 n、q、误差分布、密文失败率。第二步，选攻击面：原始攻击（Kannan 嵌入加 BKZ）、对偶攻击（SIS 短依赖，3.2 节那座桥）、穷搜秘密的小系数结构，各算一遍。第三步，读块大小：工具输出每个攻击面需要的 \beta。第四步，换算并取最小：0.292\beta 折算，所有攻击面里最便宜的档就是真实安全强度——账本永远按最薄的一页结账。

一个常见误读顺便纠正：参数表里的维数 n 不直接等于"n 位安全"。Kyber512 的 n 是 512，安全却写在 143 位一栏——因为攻击成本还受误差宽度与模数调节。把"n 换安全"理解成"n 是主旋钮但不是唯一旋钮"，是读参数表的第一课。

问题：为什么失败率也进评估输入

解密失败意味着一次"带已知明文的异常样本"，攻击者可以主动制造海量失败事件收集样本——失败率越高，可用信息越多，攻击模型越宽松。所以现代参数表把失败率压到二负几十次方量级，并把"失败率目标"作为估算工具的必填项。复习 4.1 节的判断规则 |w| > q/4：失败率就是累计噪声越过这条红线的概率，参数链从构造一路贯到评估，环环相扣。

要点速记：攻击成本约等于 2 的 0.292β 次方（量子 0.265β），块大小是安全账本的通货；误差越宽、模数越小、维数越大则 β 越大；Kyber512 的 143 与 119 两个数可用一行乘法复核；口径差异、量子进展、系数漂移是估计出人入的三处脚注，参数要按悲观口径留边际。

账本合上了。第 4 章开始花这笔钱：用预算内的参数，把加密、封装与签名一步步构造出来。