**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

[ Cryptology ePrint archive ]