**On the Complexity of the Crossbred Algorithm**

*Joćo Diogo Duarte*

**Abstract: **The Joux-Vitse Crossbred algorithm's aim is to efficiently solve a system of semi-regular multivariate polynomials. For random polynomials, this is thought to be at least hard for a classical computer to solve. In this work, the algorithm is described in detail, a bivariate generating series to test the admissibility of parameters in F_2 is investigated and from this, a new series for F_q, q > 2 is presented. In addition, a complexity estimate is given for both F_2 and F_q, q > 2, which is compared to an estimate presented by Samardijska et al. Their estimate is shown to be an upper bound for the Crossbred algorithm. By obtaining optimal parameters using the previous results, the cost of theoretically applying Crossbred, FES and Hybrid-F5 to polynomial systems of various sizes of various numbers of variables and q was plotted. Overall, it was determined that for larger fields, the Crossbred algorithm provides an improved asymptotic complexity over FES. However, it does not provide any improvement over Hybrid-F5.

**Category / Keywords: **public-key cryptography / Post-Quantum Cryptography, Multivariate Polynomial Systems, Grobner Basis, Crossbred Algorithm, Complexity

**Original Publication**** (in the same form): **Mathematical Cryptology

**Date: **received 1 Sep 2020

**Contact author: **joaodduarte at protonmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20200901:223151 (All versions of this report)

**Short URL: **ia.cr/2020/1058

[ Cryptology ePrint archive ]