Paper 2023/1664

On the Complexity and Admissible Parameters of the Crossbred Algorithm in ${\mathbb{F}}_{q\ge 2}$

Abstract

The Joux--Vitse Crossbred algorithm's aim is to efficiently solve a system of semi-regular multivariate polynomials equations. The authors tested their algorithm for boolean polynomials in ${\mathbb{F}}_2$ and stated that this algorithm also works for other non-boolean finite fields. In addition, the algorithm is dependent on a set of parameters that control its course. Finding functional parameters for this algorithm is a non-trivial task, so the authors presented a bivariate generating series to test the admissibility of parameters in ${\mathbb{F}}_2$. However, due to restrictive page limits, the series itself and its derivation are not explained. In this work, the derivation of the bivariate generating series to test the admissibility of parameters in boolean $$ is explained and from this, a new series for other non-boolean fields, $$ is presented. In addition, a complexity estimate of the algorithm is given for both $$ and $$. By obtaining optimal parameters using the previous results, the cost of applying Crossbred to polynomial systems of various sizes, numbers of variables and values of $$ was plotted. Overall, it was determined that the Crossbred algorithm provides an improved complexity over FES (Fast Exhaustive Search) for larger overdetermined systems, but for any overdetermined system, it does not improve the complexity when compared to state-of-the-art algorithms, Hybrid-$$ and FXL.

Note: Removed silly sentence about not comparing Crossbred to FXL.