Paper 2026/360

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

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.

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