Paper 2026/1382
Concrete Bit-Operation Cost of XL: For Solving Multivariate Quadratic Systems Using Wiedemann and Berlekamp-Massey
Abstract
We present a concrete bit-operation cost model for solving multivariate quadratic systems with XL using Wiedemann linear algebra, and Berlekamp-Massey sequence recovery. Following the CryptAttackTester methodology, we implement XL in a circuit-oriented model and derive closed-form cost formulas for the XL, Wiedemann, and Berlekamp-Massey steps. We instantiate the model for GF(2), GF(31), and GF(256), including baseline, constant-coefficient, and bucketed matrix-evaluation variants. Experiments on small parameter sizes show that the formulas accurately predict the circuit costs, while asymptotic analysis confirms convergence to the expected leading constant factors determined by the underlying field arithmetic. We apply the resulting estimates to Fukuoka MQ Challenge instances and to multivariate candidates from the NIST additional-signature process, providing a unified bit-operation comparison of direct Wiedemann-XL costs across several MQ-based schemes.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- XLmultivariate quadratic systemsalgebraic cryptanalysisWiedemann algorithmBerlekamp-Massey
- Contact author(s)
-
hevkan @ gmail com
ruben @ polycephaly org - History
- 2026-07-15: revised
- 2026-07-06: received
- See all versions
- Short URL
- https://ia.cr/2026/1382
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1382,
author = {Hülya Evkan and Ruben Niederhagen},
title = {Concrete Bit-Operation Cost of {XL}: For Solving Multivariate Quadratic Systems Using Wiedemann and Berlekamp-Massey},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1382},
year = {2026},
url = {https://eprint.iacr.org/2026/1382}
}
