Paper 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.

Note: See revised/corrected version at https://eprint.iacr.org/2023/1664

Metadata
Available format(s)
-- withdrawn --
Category
Public-key cryptography
Publication info
Published elsewhere. Mathematical Cryptology
Keywords
Post-Quantum CryptographyMultivariate Polynomial SystemsGrobner BasisCrossbred AlgorithmComplexity
Contact author(s)
joaodduarte @ protonmail com
History
2022-04-18: withdrawn
2020-09-01: received
See all versions
Short URL
https://ia.cr/2020/1058
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.