Welcome to the resource topic for 2023/1664
Title:
On the Complexity and Admissible Parameters of the Crossbred Algorithm in \mathbb{F}_{q\geq2}
Authors: João Diogo Duarte
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 polynomials in \mathbb{F}_2 and stated that this algorithm also works for other 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 \mathbb{F}_2 is explained and from this, a new series for \mathbb{F}_{q>2} is presented. In addition, a complexity estimate of the algorithm is given for both \mathbb{F}_2 and \mathbb{F}_{q>2}. 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 q was plotted. Overall, it was determined that for larger fields, the Crossbred algorithm does not provide an improved asymptotic complexity over FES (Fast Exhaustive Search) and a similar state-of-the-art algorithm, Hybrid-F_5.
ePrint: https://eprint.iacr.org/2023/1664
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .