Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings
Hiroki Furue, NTT (Japan)
Momonari Kudo, Fukuoka Institute of Technology
Abstract
Solving a system of multivariate quadratic equations in 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 variables are divided into variables to be fixed and the remaining variables as ``main variables'', and we generate a Macaulay matrix with respect to the main variables over a polynomial ring of the (sub-)variables. By eliminating some columns of the Macaulay matrix over the polynomial ring before guessing 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 , which is the case of general multivariate signatures. For example, on systems over the finite field with elements with , the numbers of operations deduced from the theoretical bounds of the hybrid approaches with XL and Wiedemann XL, Crossbred, and PXL with optimal are estimated as , , , and , respectively.
@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},
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.