Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings

Solving a system of m multivariate quadratic equations in n variables over finite fields (the MQ problem) is one of the important problems in the theory of computer science. The XL algorithm (XL for short) is a major approach for solving the MQ problem with linearization over a coefficient field. Furthermore, the hybrid approach with XL (h-XL) is a variant of XL guessing some variables beforehand. In this paper, we present a variant of h-XL, which we call the polynomial XL (PXL). In PXL, the whole n variables are divided into k variables to be fixed and the remaining \(n-k\) variables as “main variables”, and we generate a Macaulay matrix with respect to the \(n-k\) main variables over a polynomial ring of the k (sub-)variables. By eliminating some columns of the Macaulay matrix over the polynomial ring before guessing k variables, the amount of operations required for each guessed value can be reduced compared with h-XL. Our complexity analysis of PXL (under some practical assumptions and heuristics) gives a new theoretical bound, and it indicates that PXL could be more efficient than other algorithms in theory on the random system with \(n=m\) , which is the case of general multivariate signatures. For example, on systems over the finite field with \({2^8}\) elements with \(n=m=80\) , the numbers of operations deduced from the theoretical bounds of the hybrid approaches with XL and Wiedemann XL, Crossbred, and PXL with optimal k are estimated as \(2^{252}\) , \(2^{234}\) , \(2^{237}\) , and \(2^{220}\) , respectively.