Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal

Details:

   
TitleSolving underdetermined systems of multivariate quadratic equations revisited.
Author(s) Enrico Thomae, Christopher Wolf
TypeBook, Chapter in Book, Conference Proceeding
AbstractSolving systems of m &#57913;ultivariate &#57917;uadratic (&#57913;&#57917;) equations in n variables is one of the main challenges of algebraic cryptanalysis. Although the associated &#57913;&#57917;-problem is proven to be NP-complete, we know that it is solvable in polynomial time over fields of even characteristic if either m&#8201;&#8805;&#8201;n(n&#8201;&#8722;&#8201;1)/2 (overdetermined) or n&#8201;&#8805;&#8201;m(m&#8201;+&#8201;1) (underdetermined). It is widely believed that m&#8201;=&#8201;n has worst case complexity. Actually in the overdetermined case Gröbner Bases algorithms show a gradual decrease in complexity from m&#8201;=&#8201;n to m&#8201;&#8805;&#8201;n(n&#8201;&#8722;&#8201;1)/2 as more and more equations are available. For the underdetermined case no similar behavior was known. Up to now the best way to deal with the case m&#8201;<&#8201;n&#8201;<&#8201;m(m&#8201;+&#8201;1) was to randomly guess variables until m&#8201;=&#8201;n. This article shows how to smartly use additional variables and thus obtain a gradual change of complexity over even characteristics also for the underdetermined case. Namely, we show how a linear change of variables can be used to reduce the overall complexity of solving a &#57913;&#57917;-system with m equations and n&#8201;=&#8201;&#969;m variables for some &#969;&#8201;&#8712;&#8201;&#8474;>&#8201;1 to the complexity of solving a &#57913;&#57917;-system with only (m&#8722;&#8970;&#969;&#8971;+1) equations and variables, respectively. Our algorithm can be seen as an extension of the previously known algorithm from Kipnis-Patarin-Goubin (extended version of Eurocrypt 99) and improves an algorithm of Courtois et al. which eliminates &#8970;log2&#969;&#8971; variables. For small &#969; we also adapt our algorithm to fields of odd characteristic. We apply our result to break current instances of the Unbalanced Oil and Vinegar public key signature scheme that uses n&#8201;=&#8201;3m and hence &#969;&#8201;=&#8201;3.
KeywordsUnderdetermined Multivariate Equations, UOV Signature Scheme
ISBN978-3-642-30056-1/pbk
URL http://link.springer.com/chapter/10.1007%2F978-3-642-30057-8_10
LanguageEnglish
Pages156--171
PublisherBerlin: Springer
Year2012
Edition0
Translation No
Refereed No
Webmaster