Solving Underdetermined Systems of Multivariate Quadratic Equations Revisited

Solving systems of

m

$\mathcal M$

ultivariate

$\mathcal Q$

uadratic (

$\mathcal{MQ}$

) equations in

n

variables is one of the main challenges of algebraic cryptanalysis. Although the associated

$\mathcal{MQ}$

-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

$\mathcal{MQ}$

-system with

m

equations and

n

 = 

ωm

variables for some

ω

 ∈ ℚ

> 1

to the complexity of solving a

$\mathcal{MQ}$

-system with only

$(m-\left\lfloor \omega\right\rfloor+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

$\left\lfloor \mbox{log}_2\omega\right\rfloor$

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

 = 3

m

and hence

ω

 = 3.