Welcome to the resource topic for 2009/154
Title:
Algorithms to solve massively under-defined systems of multivariate quadratic equations
Authors: Yasufumi Hashimoto
Abstract: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 solve equations in polynomial time (see [Kipnis et al, Eurocrypt’99] and also [Courtois et al, PKC’02]). In the present paper, we give two algorithms to solve 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+1)/2+1. The first algorithm solves equations over any finite field in polynomial time. The second algorithm requires exponential time operations. However, the number of required variables is much smaller than that in the first one, and the complexity is much less than the exhaustive search.
ePrint: https://eprint.iacr.org/2009/154
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .