文章总结： 哈工大团队论文被Eurocrypt2026录用，提出Group-and-Solve攻击框架，针对Goldreich伪随机数生成器的XOR-THR谓词进行分析。该成果利用偏差放大机制和定制LPN求解器，攻破了Eurocrypt2024中SilentOT协议实例及FiLIP密码实例，解决了大局部性结构安全性难题。研究为密码原语参数选择提供了重要安全标准。
综合评分： 85
文章分类： 漏洞分析,安全大事件
哈尔滨工业大学刘川意、付希明团队研究成果被Eurocrypt 2026录用
信息网络安全杂志
2026年2月26日 17:04
上海
近日，刘川意、付希明团队的论文《Attacks on Goldreich’s Pseudorandom Generators by Grouping and Solving》被国际密码学顶级会议Eurocrypt 2026正式录用。付希明副教授为第一作者，刘川意教授为通讯作者。这是哈工大一校三区首次在密码学顶级会议上发表论文。根据CSRankings的数据，这也是哈工大一校三区首次在计算机理论（包括算法与复杂性、密码学和逻辑与验证）领域发表顶会论文（注：CSRankings将计算机学科分为人工智能、计算机系统、计算机理论和交叉学科四个领域）。
Goldreich伪随机数生成器是一类重要的密码学原语，尤其是具有多项式延展度的该类生成器在恒定冗余的安全计算、不可区分混淆 (iO)、MPC友好的密码学原语和加密胶囊领域有广泛的应用。构造该类随机数生成器的关键是构造一个具有局部性的谓词函数，其中主要构造有XOR-AND (FOCS 2003)和XOR-THR (STOC 2016)。针对XOR-AND的安全性分析，有学者提出了Guess-and-Determine和Guess-and-Decode 攻击。然而这两类攻击主要针对小局部性的谓词，且依赖于方程的稀疏性和无噪假设。然而，对于大局部性的XOR-THR结构，随着参数增长，这些方法的攻击复杂度急剧增加。因此，针对基于XOR-THR的Goldreich伪随机数生成器的安全性分析是公开难题。
本研究针对密码学界长期关注的Goldreich 伪随机数生成器（PRG）的安全性提出了强大的分析框架。特别是针对具有多项式延展度的XOR-THR谓词函数，研究团队提出的Group-and-Solve (GAS)攻击打破了现有挑战的安全性上界。该成果直接攻破了Eurocrypt 2024中用于构建高效Silent OT协议的参数实例，在PC机上实现了该实例的破解。此外，该方法还成功扩展至FiLIP 密码，揭示了多个实例达不到其声称的安全性。
本研究提出了全新的Group-and-Solve (GAS)攻击框架，通过构造并求解低噪声的含噪线性方程组来恢复随机数种子，其核心创新包括：
-
高效的偏差放大机制：
论文观察到，当 XOR-THR 谓词的部分输入位被固定时，原本平衡的非线性函数会表现出显著的不平衡性。通过将输出比特根据公共输入进行“分组”，攻击者可以获得一组偏差极大的噪声方程，从而构造了低噪声的线性方程组。显著降低 LPN 问题的求解难度。
-
定制化的LPN求解器：
含噪线性方程组求解可以规约到LPN问题，是密码学和理论计算机中的经典困难问题。针对分组后“样本量少、偏差大”的特点，研究团队改进了高斯消元法，设计了专门的求解策略。与传统的 BKW 算法相比，新方法不需要海量的内存和方程数量，完美适配了输出长度受限的约束。
-
跨方案的普适性攻击：
该框架不仅适用于Eurocrypt 2024中用于构建高效Silent OT协议的参数实例，还被成功适配到具有白化噪声结构的FiLIP 密码中，对于大多数此密码实例，攻击是成功且高效的。
该工作为基于局部函数的密码原语设计提供了安全性分析的依据。对于依赖 Goldreich PRG 的密码学原语构造，本研究提供的攻击将成为其未来参数选择的标准，对于密码学理论和应用具有重要参考价值。
该工作体现了研究团队在密码学基础理论和计算机科学中经典困难问题求解领域的创新能力，其中涉及到LPN求解和ISD求解算法更是后量子密码的基础问题。未来，团队将继续探索后量子时代下的密码安全边界，为构建更可信的数字安全基础设施提供理论支撑。
来源：HITSZ网络空间安全研究院微信公众号
信息网络安全
《信息网络安全》创刊于2001年，是由公安部主管，公安部第三研究所、中国计算机学会主办，面向国内外公开发行的国内首批信息安全类期刊之一，于2015年成为中国科技核心期刊，2017年成为中国科学引文数据库来源期刊，2018年成为中文核心期刊，2022年入选CCF计算领域高质量科技期刊分级目录。
中文核心期刊
中国科技核心期刊
中国科学引文数据库来源期刊
CCF计算领域高质量科技期刊
我们在不断努力和完善中，期待您的关注和支持！
免责声明：
本文所载程序、技术方法仅面向合法合规的安全研究与教学场景，旨在提升网络安全防护能力，具有明确的技术研究属性。
任何单位或个人未经授权，将本文内容用于攻击、破坏等非法用途的，由此引发的全部法律责任、民事赔偿及连带责任，均由行为人独立承担，本站不承担任何连带责任。
本站内容均为技术交流与知识分享目的发布，若存在版权侵权或其他异议，请通过邮件联系处理，具体联系方式可点击页面上方的联系我。
本文转载自：信息网络安全杂志 《哈尔滨工业大学刘川意、付希明团队研究成果被Eurocrypt 2026录用》