Cryptology ePrint Archive: Report 2009/154

Algorithms to solve massively under-defined systems of multivariate quadratic equations

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.

Category / Keywords: multivariate quadratic equation

Date: received 1 Apr 2009, last revised 28 Jun 2010

Contact author: hasimoto at isit or jp

Available format(s): PDF | BibTeX Citation

Note: Presented at Industrial Track in ACNS2010

Version: 20100628:234528 (All versions of this report)

Short URL: ia.cr/2009/154

Discussion forum: Show discussion | Start new discussion