Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations

摘要

It is well known that the problem to solve a set of randomly chosen multivariate quadratic equations over a finite field is NP-hard. However, when the number of variables is much larger than the number of equations, it is not necessarily difficult to solve equations. In fact, when n ≥ m(m + 1) (n, m are the numbers of variables and equations respectively) and the field is of even characteristic, there is an algorithm to find one of solutions of equations in polynomial time (see [Kipnis et al., Eurocrypt'99] and also [Courtois et al., PKC'02]). In the present paper, we propose two new algorithms to find one of solutions of quadratic equations; one is for the case of n ≥ (about)m~2 - 2m~(3/2) + 2m and the other is for the case of n > m(m + l)/2 + 1. The first one finds one of solutions of equations over any finite field in polynomial time, and the second does with O(2~m) or O(3~m) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.