【哈工大（深圳）宣】（信息学部/文）近日，哈工大深圳校区信息学部网络安全研究院刘川意教授（通讯作者）、付希明副教授（第一作者）团队论文《Attacks on Goldreich's Pseudorandom Generators by Grouping and Solving》被国际密码学顶级会议Eurocrypt 2026录用，这是哈工大首次在密码学顶级会议上发表论文。

Goldreich伪随机数生成器是一类重要的密码学原语，尤其是具有多项式延展度的该类生成器在恒定冗余的安全计算、不可区分混淆(iO)、MPC友好的密码学原语、加密胶囊、不经意传输（OT）领域有广泛的应用。构造该类随机数生成器的关键是构造一个具有局部性的谓词函数，其中主要构造有XOR-AND (FOCS 2003)和XOR-THR (STOC 2016)。针对XOR-AND的安全性分析，有学者提出了Guess-and-Determine和Guess-and-Decode攻击。然而这两类攻击主要针对小局部性的谓词，且依赖于方程的稀疏性和无噪假设。对于大局部性的XOR-THR结构，随着参数增长，这些方法的攻击复杂度接近穷举。因此，针对基于XOR-THR的Goldreich伪随机数生成器的安全性分析是公开难题。

本研究针对密码学界长期关注的Goldreich伪随机数生成器的安全性提出了强大的分析框架。特别是针对具有多项式延展度的XOR-THR谓词函数，研究团队提出的Group-and-Solve (GAS)攻击打破了现有挑战的安全性上界。该成果直接攻破了Eurocrypt 2024中用于构建高效Silent OT协议的参数实例，在PC机上实现了该实例的破解。此外，该方法还成功扩展至FiLIP密码，揭示了多个实例达不到其声称的安全性。

该团队介绍说，本研究提出的全新的Group-and-Solve (GAS)攻击框架具有三大主要创新点。一是高效的偏差放大机制，论文观察到，当XOR-THR谓词的部分输入位被固定时，原本平衡的非线性函数会表现出显著的不平衡性。通过将输出比特根据公共输入进行“分组”，攻击者可以获得一组偏差极大的噪声方程，从而构造了低噪声的线性方程组。二是定制化的LPN求解器，含噪线性方程组求解可以规约到LPN求解这一密码学经典困难问题。团队针对分组后“样本量少、偏差大”的特点改进了高斯消元法，设计了专门的求解策略，与传统的BKW算法相比，新方法不需要海量的内存和方程数量，完美适配了输出长度受限的约束。三是跨方案的普适性攻击，该框架不仅适用于Eurocrypt 2024中用于构建高效Silent OT协议的参数实例，还被成功适配到具有白化噪声结构的FiLIP密码中，对于大多数此密码实例，攻击是成功且高效的。

该工作为基于局部函数的密码原语设计提供了安全性分析的依据。对于依赖Goldreich伪随机数生成器的密码学原语构造，本研究提供的攻击将成为其参数选择的标准，对于密码学理论和应用具有重要参考价值。例如，该类随机数生成器是构造Silent OT的重要技术，而Silent OT是当前实现隐私保护机器学习的关键安全计算技术，广泛应用在隐私推理等场景中。（编辑 谢梁晖 审核 张惠屏 陈南坤）