International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

An analysis of the Crossbred Algorithm for the MQ Problem

Authors:
Damien Vidal , Laboratoire MIS, Université de Picardie Jules Verne
Claire Delaplace , Laboratoire MIS, Université de Picardie Jules Verne
Sorina Ionica , Laboratoire MIS, Université de Picardie Jules Verne
Download:
DOI: 10.62056/ak86cy7qiu
URL: https://cic.iacr.org//p/1/3/36
Search ePrint
Search Google
Abstract:

The Crossbred algorithm is currently the state-of-the-art method for solving overdetermined multivariate polynomial systems over F2. Since its publication in 2017, 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.

BibTeX
@article{cic-2024-34847,
  title={An analysis of the Crossbred Algorithm for the MQ Problem},
  journal={cic},
  publisher={International Association for Cryptologic Research},
  volume={1, Issue 3},
  url={https://cic.iacr.org//p/1/3/36},
  doi={10.62056/ak86cy7qiu},
  author={Damien Vidal and Claire Delaplace and Sorina Ionica},
  year=2024
}