Title | **Solving underdetermined systems of multivariate quadratic equations revisited.** |

Author(s) | Enrico Thomae, Christopher Wolf |

Type | Book, Chapter in Book, Conference Proceeding |

Abstract | Solving systems of m ultivariate uadratic () equations in n variables is one of the main challenges of algebraic cryptanalysis. Although the associated -problem is proven to be NP-complete, we know that it is solvable in polynomial time over fields of even characteristic if either m ≥ n(n − 1)/2 (overdetermined) or n ≥ m(m + 1) (underdetermined). It is widely believed that m = n has worst case complexity. Actually in the overdetermined case Gröbner Bases algorithms show a gradual decrease in complexity from m = n to m ≥ n(n − 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 < n < m(m + 1) was to randomly guess variables until m = 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 -system with m equations and n = ωm variables for some ω ∈ ℚ> 1 to the complexity of solving a -system with only (m−⌊ω⌋+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 ⌊log2ω⌋ variables. For small ω 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 = 3m and hence ω = 3. |

Keywords | Underdetermined Multivariate Equations, UOV Signature Scheme |

ISBN | 978-3-642-30056-1/pbk |

URL |
http://link.springer.com/chapter/10.1007%2F978-3-642-30057-8_10 |

Language | English |

Pages | 156--171 |

Publisher | Berlin: Springer |

Year | 2012 |

Edition | 0 |

Translation |
No |

Refereed |
No |