
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Algorithms to Solve Massively UnderDefined Systems of Multivariate Quadratic Equations
Yasufumi HASHIMOTO
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E94A
No.6
pp.12571262 Publication Date: 2011/06/01 Online ISSN: 17451337
DOI: 10.1587/transfun.E94.A.1257 Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: underdefined multivariate quadratic equations, multivariate public key cryptosystem, the unbalanced oil and vinegar signature scheme (UOV),
Full Text: PDF(188.8KB)>>
Summary:
It is well known that the problem to solve a set of randomly chosen multivariate quadratic equations over a finite field is NPhard. 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 find one of solutions of equations in polynomial time (see [Kipnis et al., Eurocrypt '99] and also [Courtois et al., PKC '02]). In the present paper, we propose two new algorithms to find one of solutions of 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 one finds one of solutions of equations over any finite field in polynomial time, and the second does with O(2^{m}) or O(3^{m}) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.

