论文标题
代数密码分析的正式力量系列
Formal Power Series on Algebraic Cryptanalysis
论文作者
论文摘要
在对攻击的复杂性估计中，该攻击将密码系统降低以解决多项式方程系统时，经常在隐次分析中使用规律性和第一秋季程度的上限。虽然可以在半定期假设下使用单变量的正式功率序列来轻松计算规律性，但确定第一秋季程度的上限需要研究输入系统的混凝土syzygies。在本文中，我们研究了多项式系统在足够大的场上的第一秋季程度的上限。在这种情况下，我们证明了非隔离系统的第一个秋季程度在上面是规律性的界限，并且多分级多项式系统的第一个秋季度在上面是由多变量正式功率序列确定的某个值。此外，我们为在足够大的场上计算多项式系统的第一个秋季程度提供了理论上的假设。
In the complexity estimation for an attack that reduces a cryptosystem to solving a system of polynomial equations, the degree of regularity and an upper bound of the first fall degree are often used in cryptanalysis. While the degree of regularity can be easily computed using a univariate formal power series under the semi-regularity assumption, determining an upper bound of the first fall degree requires investigating the concrete syzygies of an input system. In this paper, we investigate an upper bound of the first fall degree for a polynomial system over a sufficiently large field. In this case, we prove that the first fall degree of a non-semi-regular system is bounded above by the degree of regularity, and that the first fall degree of a multi-graded polynomial system is bounded above by a certain value determined from a multivariate formal power series. Moreover, we provide a theoretical assumption for computing the first fall degree of a polynomial system over a sufficiently large field.
