XiaoMi-AI文件搜索系统
World File Search SystemMinRank
重新审视对 MinRank 和秩解码问题的代数攻击
摘要：秩解码问题 (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 方法的复杂性。
建议的名称：QR-UOV Hiroki Furue
1简介4 1.1历史记录。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。4 1.2 QR-UOV在Asiacrypt 2021。。。。。。。。。。。。。。。。。。。4 1.3本文档的目的。。。。。。。。。。。。。。。。。。。6 2说明和参数6 2.1注释。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。7 2.2参数。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。8 3预序8 3.1用于QR-UOV的UOV的基本描述。。。。。。。。。。。8 3.2商振铃的矩阵表示。。。。。。。。9 4算法规范10 4.1生成。。。。。。。。。。。。。。。。。。。。。。。。。。。。11 4.2生成签名。。。。。。。。。。。。。。。。。。。。。。。。。13 4.3版本。。。。。。。。。。。。。。。。。。。。。。。15 4.4键和签名的表示。。。。。。。。。。。。。。。15 4.5参数集。。。。。。。。。。。。。。。。。。。。。。。。。。。。16 4.6辅助功能。。。。。。。。。。。。。。。。。。。。。。。。。18 4.7伪随机元素元素的产生。。。。。。。。20 4.8伪随机生成器。。。。。。。。。。。。。。。。。。。。。。22 4.9基本线性代数上的注释。。。。。。。。。。。。。。。。。。。。22 5性能分析22 5.1 NIST参考平台上的性能。。。。。。。。。。。22 5.2在其他平台上的性能。。。。。。。。。。。。。。。。。。25 6预期安全强度27 6.1潜在问题和安全定义。。。。。。。。。。。27 6.2安全证明。。。。。。。。。。。。。。。。。。。。。。。。。。。。。28 6.3建议参数的安全估计。。。。。。。。。。 div>。 div>。 div>33 7-攻击再次分析QR-UOV 37 7,1清晰发现攻击。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>37 7.2直接攻击。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>37 7.3对UVO的键恢复攻击。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>40 7.3.1 Kipien-Shamir攻击。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>41 7.3.2和解攻击。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。 div>。。。。。。。。41 7.3.3交叉攻击。。。。。。。。。。。。。。。。。。。。。。42 7.3.4矩形缩小攻击。。。。。。。。。。。。。。。。43 7.4多项式f的不可约性。。。。。。。。。。。。。。。。。。。。45 7.5提升方法在扩展字段上。。。。。。。。。。。。。。。。46 7.6乘以（φFx）（n）到公钥。。。。。。。。。。。。。。。49 8优点和限制51