论文指出常规综合征解码攻击成本大幅降低导致部分参数集安全强度不足

这篇来自arXiv cs.CR的论文重新评估了常规综合征解码（RSD）问题的具体硬度，发现许多广泛使用的参数集比此前估计的要容易得多。作者提出了一种改进的混合代数攻击方法，通过协调猜测阶段和线性消除步骤，消除了之前被忽视的复杂度来源，使得攻击成本显著下降。该研究不仅针对理论问题，还重新评估了基于RSD的实际应用，包括Ferret、Wolverine和committed VOLE等协议。

具体数据显示，至少每个应用中有一个参数集的安全强度低于其128位目标，损失幅度接近67位。在PCG基准测试中，针对非二进制和二进制域的攻击成本分别比之前的最佳攻击降低了29.77位和25.91位。对于Liu等人提出的修订版128位PCG参数集，评估显示其攻击成本均低于2^111次域运算。这些结果直接挑战了现有RSD实例的硬度假设，表明当前许多参数选择高估了其底层RSD实例的安全性。

事实层面，论文提供了具体的攻击算法改进细节和数值计算结果，证实了特定参数集存在安全缺口。推断层面，这意味着依赖RSD构建的零知识协议、伪随机相关生成器和MPC in the Head签名方案可能需要重新调整参数以维持预期的安全级别。猜测层面，如果行业未能及时响应，可能导致已部署系统面临潜在的理论破解风险，但这取决于攻击者是否具备实施该改进算法的工程能力。