Improved preprocessing for the Crossbred algorithm and application to the MQ problem

Paper 2026/360

Improved preprocessing for the Crossbred algorithm and application to the MQ problem

Damien Vidal

, University of Picardie Jules Verne

Claire Delaplace

, University of Picardie Jules Verne

Sorina Ionica

, University of Picardie Jules Verne, Versailles Saint-Quentin-en-Yvelines University

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.
Keywords: multivariate cryptography MQ problem Gröbner basis algorithm MQOM
Contact author(s): damien vidal @ u-picardie fr
claire delaplace @ u-picardie fr
sorina ionica @ uvsq fr
History: 2026-02-23: approved; 2026-02-22: received; See all versions
Short URL: https://ia.cr/2026/360
License: CC BY

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}
}