改进混合代数攻击降低RSD参数集安全估计

这篇来自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签名方案可能需要重新调整参数以维持预期的安全级别。猜测层面，如果行业未能及时响应，可能导致已部署系统面临潜在的理论破解风险，但这取决于攻击者是否具备实施该改进算法的工程能力。