Algorithms to Solve Massively Under-Defined Systems of Multivariate Quadratic Equations

Yasufumi HASHIMOTO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E94-A   No.6   pp.1257-1262
Publication Date: 2011/06/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E94.A.1257
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
Category: 
Keyword: 
under-defined multivariate quadratic equations,  multivariate public key cryptosystem,  the unbalanced oil and vinegar signature scheme (UOV),  

Full Text: PDF>>
Buy this Article



Summary: 
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 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) m2-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(2m) or O(3m) operations. As an application, we also propose an attack to UOV with the parameters given in 2003.