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

• HASHIMOTO Yasufumi

  Department of Mathematical Sciences, University of the Ryukyus

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

Journal

• IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences

  IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences E94-A (6), 1257-1262, 2011

  The Institute of Electronics, Information and Communication Engineers

Keywords

• under-defined multivariate quadratic equations
• multivariate public key cryptosystem
• the unbalanced oil and vinegar signature scheme (UOV)

Details

• CRID: 1390282681287005568
• NII Article ID: 10029802211
• NII Book ID: AA10826239
• DOI: 10.1587/transfun.e94.a.1257
• BIBCODE: 2011IEITF..94.1257H
• ISSN: 17451337
• ISSN: 09168508
• Web Site: http://www.jstage.jst.go.jp/article/transfun/E94.A/6/E94.A_6_1257/_pdf
• Text Lang: en
• Data Source:
  • JaLC
  • Crossref
  • CiNii Articles
• Abstract License Flag: Disallowed