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

##### Abstract

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 \textit{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 manipulations required for each guessed value can be reduced. Our complexity analysis of PXL gives a new theoretical bound, and it indicates that PXL is efficient in theory on the random system with $n=m$, which is the case of general multivariate signatures. For example, on systems over ${\mathbb F}_{2^8}$ with $n=m=80$, the numbers of manipulations deduced from the theoretical bounds of the hybrid approaches with XL and Wiedemann XL and PXL with optimal $k$ are estimated as $2^{252}$, $2^{234}$, and $2^{220}$, respectively.

Available format(s)
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
MQ problem MPKC XL hybrid approach Macaulay matrices
Contact author(s)
furue-hiroki261 @ g ecc u-tokyo ac jp
kudo @ mist i u-tokyo ac jp
History
2022-06-22: revised
See all versions
Short URL
https://ia.cr/2021/1609

CC BY

BibTeX

@misc{cryptoeprint:2021/1609,
author = {Hiroki Furue and Momonari Kudo},
title = {Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings},
howpublished = {Cryptology ePrint Archive, Paper 2021/1609},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1609}},
url = {https://eprint.iacr.org/2021/1609}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.