文章总结： 本文探讨了密码学中噪声的安全窗口问题，分析了噪声对解密的影响，讨论了安全窗口的确定因素以及采样器对安全窗口的影响，并提出了安全窗口属于整组参数的观点。
综合评分： 85
文章分类： 密码学,网络安全,安全工具,技术标准,政策法规
【密码学·采样】噪声的安全窗口：太小容易攻击，太大无法解密
原创
Litt1eQ
Litt1eQ
Coder小Q
2026年9月23日 08:30
山东
在小说阅读器读本章
去阅读
在公众号小说中沉浸阅读
【密码学·采样】噪声的安全窗口：太小容易攻击，太大无法解密
两个消息中心之间，噪声有多大余地
上一篇把 LWE 写成一组带小误差的公开线性关系。站在攻击者一侧，误差使精确方程变得难以利用；可是合法接收者最终仍要从这些带误差的量中认出消息。于是同一份噪声承担了两项方向相反的任务：它要遮住秘密，又不能把消息本身淹没。
先把具体密码方案放在一旁，只看一个模圆环上的判决问题。设模数 能被 整除，消息比特 分别放在两个相距 的中心： 与 。发送过程留下整数噪声 ，接收者看到
他把 判给圆环上较近的消息中心。两个中心之间只有半圈，正中间离任一中心都是 ，所以从正确中心出发时，安全移动半径为
本篇约定落在分界线上也计为失败。把模 的剩余类写成中心代表元后，失败事件便是
下图取 ，因此 。上半部分把中心 两侧的判决区域摊成一条数轴；两端的 与 是模圆环上的同一个消息中心。下半部分放入一条真实的离散误差和分布。大部分概率质量仍在两条边界之间，但解密失败率恰好由边界外那些很矮的红色点决定。
判决半径固定后，失败概率就是累计噪声落入两侧尾部的质量。
这张图同时提醒我们不要把“标准差不大”当成正确性的完整答案。解码器并不读取分布中心附近有多漂亮，而是在每次判决时检查随机量有没有越过边界。真正要计算的对象不是一份原始误差的平均宽度，而是最终到达判决器的随机量 及其尾部。
解密以后真正留下的是误差之和
要看清 从哪里来，只需从一种最简的 LWE 加密关系中抽出与噪声有关的部分。沿用上一篇的矩阵方向，公钥中的 份样本满足
其中 ，秘密为 ，而 的坐标来自写明的误差分布。
加密消息 时，再抽取选择向量 ，用它决定公钥样本中的哪些行参加求和。为避免把新的相关性悄悄带进公式，这里的 独立于公钥生成时已经抽到的误差 。公开的两个量写成
这不是在介绍一套完整的加密接口；它只保留了能够说明噪声怎样流动的骨架。接收者用秘密计算内积并相减：
秘密相关的线性项正好抵消，真正送到解码器的只剩消息中心与累计噪声。记
这正是 Regev 随机子集加密中出现的误差和[1]；同一关系也常用列矩阵方向来书写[2]。
固定选择向量以后， 表示被选中并参与求和的误差个数。此时 是 份误差之和；若 本身也随机，那么无条件分布还要对不同的 混合。这个区别很重要：把“平均选中多少项”直接塞进一个固定权重公式，通常得不到精确的失败概率。
小误差相加，分布会怎样改变
设两份独立整数随机变量 的概率质量函数已经知道。和为 的事件可以由所有互不相交的组合 构成，因此
右侧就是离散卷积。乘法来自 与 的独立性；如果只知道两者各自的边缘分布，却不知道它们怎样相关，这个公式便不能擅自使用。
继续使用上一篇的五点误差律：
它的均值为 、方差为 。一份误差的支撑只有 ； 份独立误差相加以后，支撑扩到 ，方差变成 ，而每个整数点上的概率由 次卷积精确给出。
下图把 放在相同坐标轴上。每个竖杆只表示一个整数点上的概率质量，杆与杆之间没有连续概率；红色虚线始终固定在 。随着参与求和的误差变多，中心变矮、分布变宽，概率质量开始向判决边界推进。
独立小误差反复卷积后，累计噪声逐渐接近固定判决边界。
在 的有限模型中， 与 的支撑尚未碰到边界，所以失败概率严格为零； 只有 两个极端点失败，概率为 ；到 时，精确尾概率约为 。这里没有进行随机模拟：这些数来自有限概率表的精确卷积。它们展示的是机制，不是任何实际方案的参数结论。
失败藏在分布的尾部
有限支撑时可以一直卷积下去，但支撑一宽，完整概率表很快变大。密码学分析还需要一种更紧凑的语言：不逐点列出分布，也能保证尾部不会太重。若一个居中的随机变量 对每个实数 都满足
就称它为次高斯随机变量（sub-Gaussian random variable），并称 为这里采用的次高斯参数。左侧是 的矩母函数；这个不等式限制了它在指数尺度上的增长速度，因而能够控制远离中心的概率。
若固定 后，选中的 份误差彼此独立，并且都满足上面的同一个参数 ，那么它们的矩母函数相乘，累计噪声得到尾界
附录会证明这个式子，并说明五点误差律在当前约定下可以取 。对 ，右侧约为 ，确实高于精确值 ：它给的是方便组合的充分上界，不是对有限分布的精确复原。
因此，精确卷积与次高斯界回答的是不同问题：精确卷积告诉我们在一个已知离散分布下尾部究竟有多少质量，次高斯界则只用参数 给出适用于整类分布的保守保证。前者更锋利却可能昂贵，后者更便于推导却会留下余量；两者都不能被一张有限样本直方图替代。
模运算还带来一个细节。次高斯式直接控制的是整数和 ，而解码事件使用 。只要 ，发生中心化失败必然先有 ，所以上式仍是一个充分上界；在图中的有限支撑 上，两种事件在 处恰好一致。误差能绕模圆环多圈时，若想得到精确概率，就必须把所有同余位置的质量重新合并。
一次很可靠，还不等于整个协议可靠
假设一次判决失败的概率至多为 。一个完整协议可能执行 次相关判决，任何一次失败都可能使整次操作失败。若把第 次失败记作事件 ，并集界给出
并集界本身不需要这些失败事件彼此独立；即使同一密钥、同一密文结构让它们相关，集合包含关系仍然成立。需要独立误差的地方在前一节：我们用它推导每一次判决的次高斯尾界。两层假设必须分开记录。
若希望 次判决中出现任何失败的概率至多为 ，把次高斯上界代入 ，可以得到一个便于核对的充分条件
它是正确性一侧的上限，不是等式，也不是唯一可用的分析。若每次选择的权重不同，可以逐次使用不同的精确尾概率；若只想保留一个式子，则应使用经过证明的最大权重，而不是未经论证地用平均权重代替。
协议输出之外还可能存在第二个观察面：失败标志、重试次数或应答时间。Majenz 与 Sisinni 在特定的离散 Gaussian 公钥加密和参数条件下，证明了针对 FFP-NG 失败接口的安全性可以归约到相应的 LWE 问题[3]。这个结果并不表示每次失败都会泄露密钥，也不适用于所有 LWE 加密或封装方案；它说明失败接口必须连同方案与攻击模型一起分析。
标准也采用这种按接口和安全声明判断的方法。FIPS 203 为其特定构造定义了解封装失败概率，但这些数值属于该构造，不能搬到本篇的有限模型中[4]。不存在脱离方案的“可接受失败率”：如果失败破坏了声称的安全性质，再小也要重新分析；若有强论证说明失败不威胁安全，它首先是可靠性和性能问题。
为什么不能把噪声一直缩小
正确性似乎偏爱更窄的误差： 变小，尾界下降，解码更可靠。但把噪声一直缩到零，上一篇已经给出了结果。此时
重新成为精确线性系统；只要公开行足够且满秩，消元就能恢复秘密。安全性一侧不能只盯着解密尾部，因为攻击者观察的是整组公开 LWE 样本。
零误差只是最明显的端点。Cueto Noval、Merz、Stählin 与 Ünal 研究的一类固定集合误差变体表明：当每个误差坐标来自固定大小的集合，并满足论文规定的有限域、特征和样本条件时，收集足够多样本可以在多项式时间内恢复秘密[5]。这个定理不能扩写成对所有窄误差、所有有界分布或所有 LWE 参数的通用攻击；它只说明“支撑非零”本身并不足以保证困难。
另一侧的困难性依据也总带着参数。Regev 的归约和后续综述把维数、模数、误差尺度、样本数以及目标格问题联系起来[1], [2]；具体攻击估计还要固定秘密分布、可用样本和攻击资源。因此安全性一侧若需要一个噪声下限，只能在固定参数与攻击模型下由外部归约或攻击分析给出，并暂记为 。本文没有推出一个普适的 ，更不能从“误差不是零”跳到“参数已经安全”。
这正是“安全窗口”比单一尾界更难的原因。正确性可以从明确的判决事件出发给出充分上限；安全性却不是一条只依赖 的初等不等式。它需要说明攻击者看见什么、允许多少样本、采用什么计算模型，以及引用的困难性结论究竟覆盖哪一类分布。
安全窗口属于整组参数
安全窗口不是只由噪声尺度决定的区间；它只能在整组参数与攻击模型固定以后讨论。在这些条件已经写清时，可以把正确性允许的最大尺度记作 ，把某项明确安全分析支持的下界记作 。如果外部分析确实给出
二者之间就存在可选区域；反之，没有一个噪声尺度能够同时满足这两项要求。下图用虚线画安全侧边界，正是为了强调它不是本篇公式自动产生的普适常数。
只有固定其余参数和观察模型后，噪声尺度才形成有意义的可用窗口。
更完整地说，窗口属于一整组输入：维数 、模数 、样本数 、误差分布族、秘密分布、公开样本数量、选择向量的权重规律、判决次数 、失败预算 以及攻击模型。改动其中任何一项，都可能移动一侧或两侧边界。即便所有这些量固定，只写一个方差或次高斯参数也未必唯一确定误差分布；安全定理若要求某个具体分布，就必须核对完整分布条件。
这也解释了工程参数表为何通常成组出现。增大 会拉开消息中心，却也改变 LWE 参数比例；减少参与求和的项数会降低累计噪声，却可能改变加密分布或安全证明；把失败预算从单次提升到整个协议，会通过 收紧正确性上限。不存在一个脱离这些关系、单独贴在采样器上的“安全噪声宽度”。
采样器一变，窗口也会移动
到这里，采样器不再只是产生一份看起来钟形的误差。它先决定公开样本的联合分布，随后经过选择、求和、模约化和判决，变成解码器与攻击者各自能够观察的随机过程。实现对目标分布的任何改动，都要沿这条路径向后追踪。
先看偏移。若每份误差都从 变成 ，而一次密文选中 项，那么累计噪声的中心从 移到 。即使单份偏移很小，它也会同方向累积；正确性分析不能继续套用居中尾界。若 公开且固定，公开样本有时可以平移校正，但这仍需在具体接口上证明，不能用“均值变化不大”一笔带过。
再看截断。剪掉远端质量往往会降低某个判决阈值下的失败概率，却同时改变公开 LWE 样本所服从的误差律。正确性一侧可能变好，原安全归约的分布前提却可能失效。反过来，两个分布即使均值和方差相同，也可以把不同概率质量放在 附近，因而具有完全不同的解密失败率。低阶矩相同，从来不等于尾部相同。
相关性改变得更彻底。若误差彼此独立， 项和的方差随 线性增长，概率律由卷积得到；若所有被选中的位置复用同一个误差，则 ，方差按 增长，而且支撑只被拉伸而没有逐渐填满。两种实现可以让每个 单独看来都服从正确分布，却把累计噪声变成两种不同随机量。这里也能看出为什么 必须独立于误差：如果选择规则偏爱绝对值大的位置，条件分布会主动加重尾部。
近似采样器需要用距离而不是目测处理。若实现输出分布与目标分布的统计距离至多为 ，确定性的求和与判决不会放大这段距离；但是许多轮独立调用形成的联合分布通常还要通过混合论证累计误差预算。若实现引入跨轮状态或相关性，逐轮边缘距离甚至不足以描述联合过程。拒绝采样中的重试上限、后备输出和可见循环次数也分别影响输出分布与侧信道观察面，不能只验证被接受样本的直方图。
因此，采样器变化以后不能只问“方差还一样吗”。应当重新写出源分布、联合关系和可见痕迹，再计算它们经过求和与判决后的尾部，并回到引用的安全分析核对分布前提。窗口不是一次计算后永久不动的刻度；它会跟着真正实现的采样过程一起移动。
结论
噪声尺度之所以同时牵动安全性与正确性，是因为同一批样本会走向两个观察面。攻击者看到公开的带误差线性关系，合法接收者看到这些误差经过选择和求和以后留下的判决量。原始误差很小，并不表示累计误差仍小；单次失败很少，也不表示整个协议和失败接口已经得到同样保证。
一份可检查的分析应当顺着随机量实际经过的路径前进：先写清采样器输出什么联合分布，再求它经过卷积、模约化和判决后的分布，最后分别核对正确性预算与固定参数下的安全依据。精确卷积、次高斯界和并集界各自承担一层工作，任何一层都不能替另一层作答。
这条路径下一步会从“误差不能暴露秘密”转向“短向量也不能暴露生成它的结构”。下一篇《SIS、陷门与短原像：为什么输出不能暴露秘密基》将讨论陷门持有者怎样采到合格短原像，同时让公开结果看不出所用的特殊基；当采样算法需要输出短向量时，怎样利用秘密基完成采样，却不让输出分布暴露这组秘密基？
附录：奇偶模数与判决边界
先设 。在模圆环上，两个消息中心为 与 。对任意接收值 ，定义它到中心 的圆距离为
发送 后有 ，所以到正确中心的距离为 。沿任一方向从正确中心移动，在到达另一个中心前恰好走过 ；两个距离相等的位置因此位于中点 。若规定距离相等时计为失败，正确判决的充分且必要条件为
其补事件就是正文采用的 。
若 为偶数但不能被 整除， 不是整数。整数格点不会恰好落在几何中点上，左右边界要按编码中心与取整规则分别写成上整或下整。若 为奇数，两个编码中心本身也只能选择为 或 附近的剩余类，两个方向的可用半径可能相差一个整数。此时不能只把正文中的 换成小数；应从实际编码中心重新比较圆距离。
最后，整数 可能绕圆多圈。中心代表元把所有 合并到同一个剩余类，所以精确失败概率应为
正文的 有限模型支撑位于 ，在 和边界计失败的约定下，这个模事件与原整数事件 一致。
附录：独立次高斯误差之和
设 相互独立，并且对每个 与所有实数 都有
令 。独立性允许把和的矩母函数拆成乘积：
对任意 ，Markov 不等式给出
右侧关于 的二次式在 处最小，因此
把同一论证用于 ，再对两个单侧事件使用并集界，得到
这里独立性只用于分解矩母函数。若各项具有不同参数 ，同样证明把分母中的 换成 。
附录：五点误差律的次高斯参数
取四个相互独立的随机符号 ，每个都以相同概率取 与 ，并令
四个正负号中正号的个数服从二项分布，所以 在 上的概率依次为
正好是正文使用的五点误差律。
单个 的矩母函数为
利用对所有实数 成立的不等式 ，可得
四项独立相加后矩母函数相乘，于是
因此在正文的约定下可以取 。直接计算也有 ，与这一尺度一致。
附录：并集界为什么不需要独立性
对任意事件 ，逐点都有示性函数不等式
左侧在至少一个事件发生时为 ；右侧此时至少为 ，若多个事件同时发生还会更大。两边取期望便得到
整个证明没有把联合概率写成乘积，因此不要求事件独立。独立性可能用于证明每个 的单独上界，也可能让人计算出更精确的联合失败概率；但它不是并集界成立的前提。
快乐的时光过得特别快，又到了说再见的时候了，咱们下次再见～
参考文献
- Regev, Oded. 2009. “On Lattices, Learning with Errors, Random Linear Codes, and Cryptography.” Journal of the ACM, 56 (6), 34:1–34:40. https://doi.org/10.1145/1568318.1568324.
- Peikert, Chris. 2016. “A Decade of Lattice Cryptography.” Foundations and Trends in Theoretical Computer Science, 10 (4), 283–424. https://doi.org/10.1561/0400000074.
- Majenz, Christian, and Fabrizio Sisinni. 2024. “Provable Security Against Decryption Failure Attacks from LWE.” Advances in Cryptology – CRYPTO 2024, Part II, Lecture Notes in Computer Science vol. 14921, 456–485, Springer. https://doi.org/10.1007/978-3-031-68379-4_14.
- National Institute of Standards and Technology. 2024. Module-Lattice-Based Key-Encapsulation Mechanism Standard. FIPS 203, U.S. Department of Commerce. https://doi.org/10.6028/NIST.FIPS.203.
- Cueto Noval, Miguel, Simon-Philipp Merz, Patrick Stählin, and Akin Ünal. 2025. “On the Soundness of Algebraic Attacks Against Code-Based Assumptions.” Advances in Cryptology – EUROCRYPT 2025, Part VI, Lecture Notes in Computer Science vol. 15606, 385–415, Springer. https://doi.org/10.1007/978-3-031-91095-1_14.
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：Coder小Q Litt1eQ
Litt1eQ《【密码学·采样】噪声的安全窗口：太小容易攻击，太大无法解密》