引言

抗量子密码学中广泛使用的带错误学习（Learning With Errors，LWE）问题已成为构建抗量子攻击密码系统的基石。然而，实际应用中攻击者往往可以利用侧信道信息获取部分秘密，从而削弱LWE的安全性。Crypto 2025的文章《Refined Attack on LWE with Hints: Constructing Lattice via Gaussian Elimination》提出了一种针对LWE问题的攻击方法，显著提升了“hints”部分秘密信息泄露时攻击LWE的效率和成功范围。本文将对该论文的核心贡献、攻击方法、技术创新及实际影响进行解读，分析其安全影响与攻击边界的变化，并探讨其对同态加密、签名等LWE应用的潜在风险影响，以及对未来格密码设计的启示。

研究背景

LWE问题由Regev提出，因难以被量子算法解决而被广泛用于构建抗量子密码方案。典型LWE假设中，攻击者只能获得通过公钥加密或协议产生的LWE样本。然而在现实中，侧信道攻击（如电磁辐射、功耗分析等）可能泄露关于秘密密钥的部分信息，例如密钥向量的某些线性组合或近似值。这类部分泄露信息在学术界通常被抽象为“hints”来研究。分析LWE面对侧信道的抗性已成为抗量子密码标准化中的关键问题之一，许多工作试图量化泄露信息对LWE安全性的影响。

早期对LWE侧信道的分析多采用定制方法，往往需要大量泄露才能破解系统。直到Dachman-Soled等人提出了首个系统化框架，将各种侧信道泄露统一抽象为提示参数进行研究。在该框架中，不同类型的提示包括：完美提示（例如获取了形式为 的精确线性信息）、模运算提示（ ）、mod-q提示（ ）以及近似提示（ ，含有一定误差）等。这一先驱性工作（以下简称DDGR方法）证明了将提示集成到LWE攻击中的原理，并能够处理多种形式的提示，但其缺点是一次只能处理一个提示，当提示数量很多时需要重复构造格攻击，每个提示都要计算两次对偶格，开销巨大。

随后，May和Nowakowski提出改进框架（以下简称MN方法），尝试一次性整合所有提示以提高效率。特别地，对于mod-q类型的提示，MN方法引入了线性代数技巧：给定 个提示，可将LWE问题的格维度从 降至 ，相当于直接利用提示线性约束削减了待求秘密的自由度。这使某些类型提示的集成更高效，并据此发现了“提示过多（too many hints）”情形：当提示数量足够大时，破解LWE将变得实际可行。然而，MN方法并非万能：对于完美提示和模减少提示仍需依赖LLL算法构造格，速度依然缓慢，而且其正确性依赖于对LWE系数矩阵“质量”的假设，需要通过人为放大矩阵系数来满足算法要求。总的来说，以往框架要么效率不佳（逐个集成提示），要么适用性受限（只对特定提示类型有效且需额外假设）。因此，学界期待一种既高效又通用的提示处理方法，并希望能量化提示对LWE硬度的影响，为评估安全性提供指引。

主要成果与技术亮点

该论文针对上述挑战，提出了全新的LWE附加提示攻击框架和技术方案，主要成果与亮点包括：

• 统一的提示处理框架：作者设计了一种通用方法，在最低假设下即可同时处理完美提示、模运算提示、mod-q提示和近似提示等各种形式的泄露信息。不同于以往方法需分类对待或逐个整合提示，新框架将提示的信息从LWE问题中解耦出来，首先独立提取提示所包含的秘密信息，再与LWE样本结合解决。这一解耦通过构造一个特殊的Z-SIS问题（整数解最短向量问题的变种）来实现：从提示导出一个SIS格，其秘密向量恰与原LWE密钥相同。这样，提示提供的额外信息被充分提炼出来，为后续攻击做好准备。
• 高斯消元构造格的新技术：在整合提示与原始LWE样本时，作者创新性地仅对较小的子矩阵执行高斯消元（将其化为行阶梯形），据此构造出攻击所需的目标格。这一过程等价于对提示对应的Z-SIS基进行行简化，然后再融入LWE的矩阵，从而将LWE带提示问题转化为标准格问题SVP（Shortest Vector Problem）的实例。相比之下，早期方法需要对整个高维格执行LLL或BKZ等基规约算法，计算量极大。高斯消元（行阶梯形，REF）处理使得格构造更加直接、高效，同时结果具有确定的正确性保证。正如作者比较所示：DDGR方法依赖昂贵的对偶格计算，MN方法需要LLL规约且要平衡矩阵块大小，而新方法通过REF精简子矩阵，在理论正确性的前提下兼顾了效率。这一技巧免除了全尺寸格规约，大幅降低了时间复杂度，也使提示信息对攻击能力的贡献更加直观。
• 理论正确性与最小假设：新框架提供了严格的非启发式正确性证明，证明攻击成功仅需极弱的条件假设。这意味着方法在理论上可靠，不像某些先前工作依赖经验参数调优或额外假设。更重要的是，该方法能够统一解释不同类型提示对LWE求解的帮助。无论提示是精确泄露一个线性关系，还是模掉一部分信息，抑或包含噪声的近似值，均可纳入统一框架处理。这使得安全分析不再割裂，而是可以在同一平台下评估各种侧信道泄露的影响。
• LWE强度下降的定量评估：为了解提示对LWE安全性的影响，作者引入了一个复杂度估计器。该估计器评估由提示构造的Z-SIS格性质，量化新格中最短向量的长度变化，从而推断破解LWE所需的算法参数（如BKZ算法的区块大小）。通过这个模型，可以预测给定数量和质量的提示会如何降低LWE的破解难度。例如，研究发现当提示数量约为密钥维度的一半时，单靠这些提示就足以重建秘密向量，无需任何额外的LWE样本。也就是说，在这种“过半提示”情况下，LWE问题几乎被降维为一个简单的线性方程组求解问题，秘密钥已经暗含在提示信息之中。这一发现严格界定了提示对安全性的“临界点”，为后续分析提供了定量依据。
• 显著的性能提升与实验验证：新方法在实际攻击效率上取得了重大进展。作者将其实现与DDGR、MN方法进行对比，在多种实例上验证优势。例如，在标准格密码方案CRYSTALS-KYBER 512（NIST选定的格基密钥交换方案）上，新方法构造攻击格仅需不到1分钟，而DDGR方法耗时超过100分钟，MN方法也需1到100分钟不等。整体攻击（包括后续格求解）同样加速显著：对KYBER-512，如果攻击者掌握200个完美提示（模拟从侧信道获得的泄露），则恢复密钥的时间从约7小时锐减到1小时以内。这意味着在相当有限的时间内（不到一小时），攻击者即可完成对密钥的重建。此外，作者还将该框架应用于模拟实际功耗侧信道的场景：通过仿真电源分析攻击产生的提示数据，验证新方法能够在“提示很多”时直接从泄露信息中提取密钥。这些实验结果充分证明了该方法的实用性和相对以往方法的巨大改进。

安全影响分析

上述研究在安全性方面的影响是多层面的。首先，攻击边界被大幅推进：过去，人们认为需要非常大量甚至接近完整密钥信息的泄露才能有效破解LWE。然而该方法证明，只要泄露的提示达到密钥维度约50%，无须任何正常密文样本即可恢复全部密钥。换言之，在提示量达到“一半”这一临界点时，LWE问题的剩余不确定性已经不足以支撑安全性，攻击者可以直接构造出秘密向量。这将“安全/不安全”的分界线清晰地划定：超过这一提示阈值，系统基本失守；而即使低于这一阈值，新攻击框架也能充分利用每一条提示来显著降低破解难度。

其次，该方法展示出部分泄露信息的威力远超预期。以往某些被认为“不完整”或“带噪”的信息，如模掉一部分的线性关系或含有误差的估计值，可能被认为对攻击帮助有限。然而通过新框架的统一处理，这些模糊提示都能转化为对秘密的有效约束，成为加速攻击的助力。特别是作者将近似提示纳入框架，说明即使侧信道得到的只是秘密的近似值或带噪声的观测，也可以通过Z-SIS转化，几乎同样用于削弱LWE的硬度。这提醒我们，任何看似细微的密钥泄露都不应掉以轻心——在高级攻击算法的利用下，点滴泄露也可能被累积放大为巨大的安全隐患。

攻击效率的提升意味着侧信道威胁的现实危险性增加。过去，即使攻击者获得了一些密钥提示信息，可能还需要耗费巨大计算资源（例如长时间运行BKZ算法）才能真正破译密钥。这在一定程度上为实际防御提供了一道“计算门槛”保护。然而新方法将这一门槛显著降低：例如在Kyber-512案例中，几乎40%的密钥信息（200/512）泄露就使得破解在一小时内完成。如此一来，如果攻击者具备适度的并行计算能力甚至专业破解设备，那么只要获取到足够提示信息，就能在很短时间内完成攻击。这对现实系统的意义在于：侧信道攻击由实验室走向实用的难度降低了。当今许多基于LWE的方案（如加密通信、FHE云计算等）会重复使用长生命周期的密钥，攻击者有充裕时间反复收集侧信道信号。一旦累积的泄露达到上述阈值范围，新的攻击方法将使得密码系统瞬间崩溃。

具体而言，在全同态加密（FHE）中，秘钥通常长期驻留在计算设备中执行大量同态操作。如果攻击者通过功耗或电磁分析逐步获取了一半左右的密钥信息，那么根据该研究，他们几乎可以立即解密所有先前截获的密文，彻底破坏FHE提供的数据隐私。同样地，对于基于LWE的公钥加密/KEM方案（如Kyber），如果设备解密时泄露出部分秘密多项式系数，攻击者在若干次解密操作后即可集齐足够提示，进而重构私钥，导致密钥交换或机密通信失陷。数字签名方面，一些格签名方案（如Dilithium）的私钥参与签名运算，多次签名中的微小信息（如某些系数的最低有效位泄露）都有可能被收集归纳为提示。利用该方法，攻击者将能把这些泄露整合为一个格攻击问题，从而比以前任何时候都更快地恢复签名私钥，造成伪造签名的风险。值得注意的是，近年来研究者已观测到Dilithium等方案在侧信道下可能泄露一部分密钥信息；而该新方法的出现，使得这类部分泄露可以更直接地转化为实用攻击。因此，所有基于LWE假设的密码应用在侧信道环境下的安全边界都需要重新审视。设计者不能再假设“小部分信息泄露无关痛痒”，因为新攻击显示即使不完整的信息也足以动摇安全根基。

这项研究通过引入提示处理的新利器，极大丰富了对LWE安全性的认知：我们现在对“需要多大泄露才能攻破LWE”有了更清晰且偏悲观的答案。这对实践的启示是明确的：哪怕攻击者只能得到秘密的一小部分线索，剩余未泄露部分所提供的安全裕度也比想象中要低。密码设计与实现领域需要认真对待这一点，在评估方案安全性时，将侧信道泄露因素纳入威胁模型加以考虑。

对未来设计的启示

面对上述攻击和分析，未来的格密码设计与实现需要在抗泄露性方面做出改进和策略调整。以下是基于该研究给出的若干反思与建议：

• 侧信道防护贯穿设计始终：开发抗量子密码方案时，应从算法设计阶段就考虑可能的侧信道泄露。正如业内共识，只有充分了解攻击者可能获得的数据，才能设计有效的防护。具体而言，算法应避免产生易被利用的线性关系或敏感中间值。例如，尽量减少密钥参与明文线性运算的次数，或者在算法中引入随机扰动使得每次操作的密钥相关信息有所不同，降低重复泄露累积出完整信息的可能性。
• 安全实现与硬件防护：在实现层面，采用成熟的侧信道对抗技术是必要的。恒定时间程序（避免根据秘密分支或访问内存）、随机掩码（对敏感变量加入随机噪声掩盖真实值）、噪声注入和功率均衡（使功耗与数据无关）等都是常见手段。这些措施可以大幅削减攻击者获取高质量提示的渠道，使其难以达到攻击阈值。对于格密码中特有的操作（如NTT变换、采样算法），已有研究提出专门的防御方案，应在实现中予以采用。另外，硬件上可以结合屏蔽和监测技术，比如在芯片中加入泄露监测，发现可疑的功耗模式时采取保护动作，从而提高攻击难度。
• 秘钥生命周期管理：基于本研究揭示的“提示数量阈值”概念，设计者应重新审视密钥的使用策略。对于长期密钥（如FHE的主密钥或KEM的私钥），如果环境可能有侧信道风险，宜定期轮换密钥或对密钥做刷新，避免单一密钥无限期使用累积泄露。此外，可以考虑采用密钥分割或门限方案：将秘密密钥拆分为多份由不同模块持有或不同时间段使用，这样即使某一路径泄露，也不至于一下子获取大量提示信息。总之，应尽量使攻击者难以通过一个固定密钥反复观测来堆积大量泄露。
• 参数选取与冗余安全度：在选择安全参数（如LWE维度、模数大小等）时，应当考虑潜在泄露情景下的安全裕度。比如，如果一种方案在无泄露时有 位安全强度，那么设计者应思考：假如攻击者获得了 的密钥信息，这一强度会下降到什么水平？新的复杂度估计器提供了量化工具。或许有必要提高某些参数以增加对抗部分泄露的余量，确保即使有小比例泄露，剩余问题仍非易事。当然，盲目加大参数会影响性能，设计者需在安全和效率间权衡。但至少，在参数报告中可以加入“在泄露Y比特信息时仍保持的安全强度”这样的数据，以提升方案面对现实攻击的可信度。
• 持续的攻防研究：该研究表明，将理论攻击与实际泄露相结合是非常有效的思路。未来攻击者可能会进一步改进提示利用算法，或者找到新的侧信道源获取提示；而防御者则需要开发更先进的对抗措施，以及探索“抗泄露”密码体制（leakage-resilient cryptography）的可能性等。

总结与展望

这项研究以高斯消元巧妙融合侧信道提示信息，显著降低了LWE问题在部分密钥泄露情形下的破解复杂度。它在继承前人工作的基础上，实现了更通用、高效且有理论保证的提示集成攻击方法，一举将LWE抗侧信道分析推进到了新高度。通过该方法，我们首次清晰地看到了LWE安全性因部分泄露而“坍塌”的临界点，以及在接近临界点处安全裕度的快速下降。这不仅对学术研究具有意义，也对实际系统的安全评估敲响了警钟。

展望未来，随着格密码逐步走向实用化，这类结合侧信道的攻击研究将越来越重要。所幸的是，攻击方法的改进也为防御提供了方向：我们更了解攻击者的能力边界，从而可以有针对性地加强防护。可以预见，在抗量子密码标准实施后，实际装备中的侧信道攻防将成为焦点，新方法或将应用于评估设备安全等级。一方面，密码工程师需要运用本文等研究的成果，完善抗侧信道的设计与实现；另一方面，研究人员也可能将类似思路拓展到其他格问题（如Ring-LWE、SIS）或其它密码体制的泄露分析中。总之，这项攻击工作为我们提供了宝贵的洞见：即使是被寄予厚望的格密码，其安全性也绝非高枕无忧，唯有同时注重数学安全性和实现安全性，方能真正构建起对抗量子计算和现实攻击的坚固防线。

参考文献

1. Cao, J., Jiang, H., Cheng, Q. (2025). Refined Attack on LWE with Hints: Constructing Lattice via Gaussian Elimination. In: Tauman Kalai, Y., Kamara, S.F. (eds) Advances in Cryptology – CRYPTO 2025. CRYPTO 2025. Lecture Notes in Computer Science, vol 16000. Springer, Cham. https://doi.org/10.1007/978-3-032-01855-7_13

联系与合作：微信号mmtoutiao

稿件来源：<密码头条技术专家组>