SCIS 2022
2022 Symposium on
Cryptography and Information Security
Osaka, Japan & Online, Jan. 18 – 21, 2022
The Institute of Electronics,
Information and Communication Engineers

Copyright ©2022 The Institute of Electronics,
Information and Communication Engineers

A New Eﬃcient Variant of the XL Algorithm Using the Arithmetic
over Polynomial Matrices
Hiroki Furue ∗Momonari Kudo ∗Keywords: MQ problem, MPKC, XL, hybrid approach, Macaulay matrices
and generate the Macaulay matrix over Fq [x1 , . . . , xk ].
The main idea of PXL is to partly perform Gaussianelimination on the matrix over the polynomial ring before ﬁxing the k variables and complete the elimination
after ﬁxing. By doing so, we can reduce the amount ofmanipulations for each guessed value compared with hXL. This enables us to solve the system more eﬃciently
for some parameters.
We also discuss the estimation of the time and spacecomplexities and compare them with those of h-XL andh-WXL. Comparing the time complexities, we showthat the proposed algorithm is more eﬃcient in thecase of n ≈ m. For example, on the system over F28
with n = m = 80, the number of manipulations in Fq
required by h-XL, h-WXL, and PXL is estimated as2252 , 2234 , and 2220 , respectively. On the other hand,in terms of the space complexity, the proposed algorithm is not well compared to WXL. Therefore, therelationship between PXL and WXL can be seen as atrade-oﬀ between time and memory.

Abstract
Solving a system over a ﬁnite ﬁeld is one of themost major problems in the ﬁeld of computer science.
Especially, the problem of solving a quadratic system(the MQ problem) is used to construct various cryptographic systems such as Rainbow and GeMSS. Given aquadratic polynomial system F in n variables x over aﬁnite ﬁeld Fq of q elements, the purpose of this researchis to ﬁnd a solution to F(x) = 0 ∈ Fmq .
One of major strategies to solve the MQ problem
is linearization, and the most basic linearization-basedalgorithm is the XL algorithm proposed by Courtois etal. [2]. XL ﬁnds a solution by generating a Macaulay
matrix at certain degree and performing Gaussian elimination on the matrix. Furthermore, Yang et al. [5] analyzed a variant of the XL algorithm called Wiedemann
XL (WXL), which adopts Wiedemann’s algorithm [3]instead of the Gaussian elimination in the XL framework.
The hybrid approach [1, 4] is an approach applying
XL eﬃciently, which mixes exhaustive search and an
MQ solver. In the hybrid approach, k variables areﬁxed, and the remaining system in n − k variables aresolved by an MQ solver. These processes are iterated
until a solution is found. In the case of n ≈ m, thehybrid approach may be eﬀective, since the gain obtained by working on systems with less variables may
overcome the loss due to the exhaustive search on theﬁxed variables. In this paper, we call the hybrid approach with XL (resp. WXL) h-XL (resp. h-WXL).
In this study, we propose a new variant of the XL algorithm, which we call the polynomial XL (PXL). PXLis constructed by improving h-XL. For the MQ system
F of m equations in n variables x = (x1 , . . . , xn ) overFq , PXL ﬁrst sets the number k of guessed variables asin the hybrid approach. We then regard the given system as a system in n − k variables xk+1 , . . . , xn , whose
coeﬃcients belong to the polynomial ring Fq [x1 , . . . , xk ],References[1] Bettale, L., Faugère, J.-C., Perret, L., “Hybrid approach for solving multivariate systems over ﬁniteﬁelds,” J. Math. Cryptol. 3, pp. 177–197 (2009)[2] Courtois, N., Klimov, A., Patarin, J., Shamir, A.,“Eﬃcient algorithms for solving overdeﬁned systems of multivariate polynomial equations,” EUROCRYPT 2000, pp. 392–407 (2000)[3] Wiedemann, D. H., “Solving sparse linear equations
over ﬁnite ﬁelds,” IEEE Trans. Inf. Theor. 32(1),pp. 54–62 (1986)[4] Yang, B.-Y., Chen, J.-M., Courtois, N., “Onasymptotic security estimates in XL and Gröbner
bases-related algebraic cryptanalysis,” ICICS 2004,
pp. 401–413 (2004)[5] Yang, B.-Y., Chen, O.C.-H., Bernstein, D.J., Chen,J.-M., “Analysis of QUAD,” FSE 2007, pp. 290–308(2007)∗ Department of Mathematical Informatics, Graduate School ofInformation Science and Technology, The University of Tokyo,
7-3-1, Hongo, Bunkyo-ku, Tokyo, 113-8656, Japan, (furuehiroki261@g.ecc.u-tokyo.ac.jp, kudo@mist.i.u-tokyo.ac.jp)1