  In cryptography, by attacks reducing a cryptosystem to the problem that
solves the system of polynomial equations, several cryptosystems have been
broken. The efficiency of an algorithm to solve the polynomial system depends
on the solving degree, and its complexity is estimated using a theoretical
proxy for the solving degree. If a polynomial system generated by an attack is
semi-regular, the degree of regularity determined from a certain univariate
formal power series is used as such a proxy, otherwise, the first fall degree
is used. In this article, we mainly investigate an upper bound for the proxy
defined using non-constructive syzygies such as the first fall degree. In
particular, for a sufficiently large field, we prove that the first fall degree
of a non-semi-regular system is bounded above by the degree of regularity of
the semi-regular system, 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 show that the assumption for the
order of a coefficient field in our results is satisfied in actual attacks
against multivariate cryptosystems. Furthermore, we provide the theoretical
assumption for the algorithm with a kernel search to solve a multi-graded
polynomial system and compute a certain proxy for the solving degree by the
multivariate formal power series. Consequently, we clarify the relationship
between the first fall degree and the degree of regularity over a sufficiently
large field, and provide a theoretical method using a multivariate power series
for cryptanalysis.
