An analysis of the Crossbred Algorithm for the MQ Problem

The Crossbred algorithm is currently the state-of-the-art method for solving overdetermined multivariate polynomial systems over <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:msub> <mml:mi>𝔽</mml:mi> <mml:mn>2</mml:mn> </mml:msub> </mml:mrow> </mml:math>. 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.