2026-11-12,来自信息工程大学的研究团队在IACR ePrint公开《Optimized Solving Strategy and Two-Step Estimator for LWE with Hints》。工作研究的是攻击者已经获得大量线性“提示”后的Learning With Errors问题,提出先做BKZ格基约化、再以BGJ筛法完成搜索的两阶段优化,并配套估算成功率和资源消耗。
作者的新增点在于不固定一套约化参数,而是联合选择BKZ块大小、tour次数和最终筛法配置。估算器先预测约化后基的轮廓,再计算秘密恢复概率和时间、内存约束,据此挑选满足目标成功率的组合。它试图避免只优化前半段或沿用通用成本模型造成的保守估计。
在论文给出的实验中,使用BLASterBKZ与BGJ筛法时,带190条完美提示的CRYSTALS-KYBER 512测试实例约7分钟恢复秘密;使用64线程和170条完美提示时约82分钟。作者还报告Kyber768测试在约325至330条完美提示下进入数小时量级。测试平台包含Intel Xeon Gold 6254处理器和192 GB内存,数字必须连同硬件、线程与提示条件一起阅读。
最重要的限制是,这不是对ML-KEM或Kyber正常部署的直接破解。所谓“完美提示”意味着攻击者已经从侧信道或其他泄漏渠道得到高质量线性信息;论文优化的是此后剩余格问题的求解。若实际设备没有对应泄漏、提示含噪声或提示数量不足,文中分钟或小时级结果不能直接套用。
对实现安全的意义在于,侧信道评估不能只判断是否泄漏,还要估计泄漏与后续密码分析组合后的端到端代价。论文结果提示:当高质量提示累计到一定数量时,传统上看似昂贵的格求解可能迅速进入工程可行范围,因此掩码、常数时间实现、采样与NTT路径的泄漏测试应与参数安全评估联动。
量仔观察
受影响的是ML-KEM实现团队、侧信道实验室和硬件评估者,而不是所有协议用户。证据来自原始论文与可复核实验条件,但提示模型仍理想化,尚缺真实设备端到端复现。建议把论文估算器用于“泄漏后成本”压力测试,同时避免宣称算法本身失效;下一观察点是带噪提示、真实采集轨迹和独立复现实验。
