Formal Power Series on Algebraic Cryptanalysis
This work provides theoretical bounds for cryptanalysis complexity, but it is incremental as it builds on existing formal power series methods.
The paper tackles the problem of bounding the first fall degree in algebraic cryptanalysis, proving that for non-semi-regular systems over sufficiently large fields, it is bounded above by the degree of regularity, and for multi-graded systems, it is bounded by a value from multivariate formal power series.
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.