机构名称：
¥ 4.0
摘要：秩解码问题 (RD) 是基于秩的密码学的核心。进入 NIST 后量子标准化进程第二轮的 ROLLO 和 RQC 等密码系统以及 Durandal 签名方案都依赖于它或其变体。该问题也可以看作是 MinRank 的结构化版本，MinRank 在多变量密码学中无处不在。最近，[16,17] 提出了基于两种新代数建模的攻击，即特定于 RD 的 MaxMinors 建模和一般适用于 MinRank 的 Support-Minors 建模。两者都显著降低了针对这两个问题的代数攻击的复杂性。在 RD 的情况下，与迄今为止的看法相反，这些新攻击被证明能够胜过组合攻击，即使在非常小的域大小下也是如此。然而，我们在此证明，[17] 中对其中一种攻击进行的分析过于乐观，该攻击包括将 MaxMinors 模型与 Support-Minors 模型混合以解决 RD，这会导致低估整体复杂性。这是通过展示这些方程之间的线性依赖关系并考虑这些模型的 F qm 版本来实现的，事实证明，这有助于更好地理解这两个系统。此外，通过对 F qm 而不是 F q 进行操作，我们能够大幅减少系统中变量的数量，并且我们 (i) 仍然保留足够的代数方程来求解系统，(ii) 能够严格分析我们方法的复杂性。对于某些参数，这种新方法可能会改进 [16,17] 中旧的 RD MaxMinors 方法。我们还介绍了一种针对 Support-Minors 系统的新混合方法，它的影响更为普遍，因为它适用于任何 MinRank 问题。这种技术显著提高了针对小型到中型场地规模的 Support-Minors 方法的复杂性。
重新审视对 MinRank 和秩解码问题的代数攻击
主要关键词
相关文件推荐
