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

Yasufumi Hashimoto

Paper 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.

Note: Presented at Industrial Track in ACNS2010

Metadata

Available format(s): PDF
Publication info: Published elsewhere. Unknown where it was published
Keywords: multivariate quadratic equation
Contact author(s): hasimoto @ isit or jp
History: 2010-06-28: last of 3 revisions; 2009-04-07: received; See all versions
Short URL: https://ia.cr/2009/154
License: CC BY

BibTeX

@misc{cryptoeprint:2009/154,
      author = {Yasufumi Hashimoto},
      title = {Algorithms to solve massively under-defined systems of multivariate quadratic equations},
      howpublished = {Cryptology {ePrint} Archive, Paper 2009/154},
      year = {2009},
      url = {https://eprint.iacr.org/2009/154}
}