Paper 2024/992
The Complexity of the Crossbred Algorithm
Abstract
The Crossbred algorithm is currently the state-of-the-art method for solving overdetermined multivariate polynomial systems over $\mathbb{F}_2$. Since its publication in 2015, several record breaking implementations have been proposed and demonstrate the power of this hybrid approach. Despite these practical results, the complexity of this algorithm and the choice of optimal parameters for it are difficult open questions. In this paper, we prove a bivariate generating series for potentially admissible parameters of the Crossbred algorithm.
Metadata
- Available format(s)
-
PDF
- Category
- Attacks and cryptanalysis
- Publication info
- Preprint.
- Keywords
- Gröbner basispolynomial systemMQ problemexhaustive searchCrossbred
- Contact author(s)
-
damien vidal @ u-picardie fr
sorina ionica @ u-picardie fr
claire delaplace @ u-picardie fr - History
- 2024-06-20: approved
- 2024-06-19: received
- See all versions
- Short URL
- https://ia.cr/2024/992
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/992, author = {Damien VIDAL and Sorina IONICA and Claire Delaplace}, title = {The Complexity of the Crossbred Algorithm}, howpublished = {Cryptology ePrint Archive, Paper 2024/992}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/992}}, url = {https://eprint.iacr.org/2024/992} }