Paper 2023/1664

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

João Diogo Duarte, Royal Holloway University of London, University of Porto
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 $\mathbb{F}_2$ is explained and from this, a new series for other non-boolean fields, $\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 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-$F_5$ and FXL.

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Post-Quantum CryptographyMultivariate Polynomial SystemsGrobner BasisCrossbred AlgorithmComplexity
Contact author(s)
joao @ diogoduarte pt
History
2024-01-18: last of 5 revisions
2023-10-26: received
See all versions
Short URL
https://ia.cr/2023/1664
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1664,
      author = {João Diogo Duarte},
      title = {On the Complexity and Admissible Parameters of the Crossbred Algorithm in $\mathbb{F}_{q\geq2}$},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1664},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1664}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.