An analysis of the Crossbred Algorithm for the MQ Problem

Damien Vidal; Sorina Ionica; Claire Delaplace

Paper 2024/992

An analysis of the Crossbred Algorithm for the MQ Problem

Damien Vidal

, University of Picardie Jules Verne

Sorina Ionica

, University of Picardie Jules Verne

Claire Delaplace

, University of Picardie Jules Verne

Abstract

The Crossbred algorithm is currently the state-of-the-art method for solving overdetermined multivariate polynomial systems over $F_{2}$ . Since its publication in 2015, several record breaking implementations have been proposed and demonstrate the power of this hybrid approach. Despite these practical results, the complexity of this algorithm and the choice of optimal parameters for it are difficult open questions. In this paper, we prove a bivariate generating series for potentially admissible parameters of the Crossbred algorithm.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published by the IACR in CIC 2024
DOI: https://doi.org/10.62056/ak86cy7qiu
Keywords: Gröbner basis polynomial system MQ problem exhaustive search Crossbred
Contact author(s): damien vidal @ u-picardie fr
sorina ionica @ u-picardie fr
claire delaplace @ u-picardie fr
History: 2024-10-10: last of 2 revisions; 2024-06-19: received; See all versions
Short URL: https://ia.cr/2024/992
License: CC BY

BibTeX

@misc{cryptoeprint:2024/992,
      author = {Damien Vidal and Sorina Ionica and Claire Delaplace},
      title = {An analysis of the Crossbred Algorithm for the {MQ} Problem},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/992},
      year = {2024},
      doi = {https://doi.org/10.62056/ak86cy7qiu},
      url = {https://eprint.iacr.org/2024/992}
}