Paper 2026/360 Original: eprint.iacr.org/2026/360 ↗
Improved preprocessing for the Crossbred algorithm and application to the MQ problem
Abstract
First, we correct certain omissions in the literature on the complexity analysis of Crossbred and give a full analysis of this algorithm. Secondly, we propose a criterion to reduce the number of polynomials generated in the preprocessing step for a set of admissible parameters $D$, $d$ and $k$, whenever this step of the algorithm produces more polynomials than necessary. We conclude by applying this criterion to the security of MQOM.
Metadata
- Available format(s)
PDF- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- History
- 2026-02-22: last updated
- 2026-02-22: published
- Short URL
- https://ia.cr/2026/360
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2026/360,
author = {Damien Vidal and Claire Delaplace and Sorina Ionica},
title = {Improved preprocessing for the Crossbred algorithm and application to the MQ problem},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/360},
year = {2026},
url = {https://eprint.iacr.org/2026/360}
}