Welcome to the resource topic for 2021/1609
Title:
Polynomial XL: A Variant of the XL Algorithm Using Macaulay Matrices over Polynomial Rings
Authors: Hiroki Furue and Momonari Kudo
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.
ePrint: https://eprint.iacr.org/2021/1609
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .