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},
note = {\url{https://eprint.iacr.org/2009/154}},
url = {https://eprint.iacr.org/2009/154}
}
