近日，刘川意、付希明团队的论文《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求解算法更是后量子密码的基础问题。未来，团队将继续探索后量子时代下的密码安全边界，为构建更可信的数字安全基础设施提供理论支撑。
（审批 付希明）
