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

*Hiroki Furue and Momonari Kudo*

**Abstract: **Solving a system of $m$ multivariate quadratic equations in $n$ variables (the $\mathcal MQ$ problem) is one of the main challenges of algebraic cryptanalysis. The XL algorithm (XL for short) is a major approach for solving the $\mathcal 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 the Macaulay matrix with respect to the $n-k$ main variables over a polynomial ring of the $k$ variables. By eliminating some columns of the Macaulay matrix over the polynomial ring before guessing $k$ variables, the amount of manipulations required for each guessed value can be reduced. Our complexity analysis indicates that PXL is efficient on the system with $n \approx m$. For example, on systems over ${\mathbb F}_{2^8}$ with $n=m=80$, the number of manipulations required by the hybrid approaches with XL and Wiedemann XL and PXL is estimated as $2^{252}$, $2^{234}$, and $2^{220}$, respectively.

**Category / Keywords: **MQ problem, MPKC, XL, hybrid approach, Macaulay matrices

**Date: **received 9 Dec 2021

**Contact author: **furue-hiroki261 at g ecc u-tokyo ac jp

**Available format(s): **PDF | BibTeX Citation

**Version: **20211209:193154 (All versions of this report)

**Short URL: **ia.cr/2021/1609

[ Cryptology ePrint archive ]