Cryptology ePrint Archive: Report 2020/1058

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 ]