Admissible Parameter Sets and Complexity Estimation of Crossbred Algorithm

Shuhei Nakamura

Paper 2023/1687

Admissible Parameter Sets and Complexity Estimation of Crossbred Algorithm

Shuhei Nakamura, Ibaraki University

Abstract

The Crossbred algorithm is one of the algorithms for solving a system of polynomial equations, proposed by Joux and Vitse in 2017. It has been implemented in Fukuoka MQ challenge, which is related to the security of multivariate crytography, and holds several records. A framework for estimating the complexity has already been provided by Chen et al. in 2017. However, it is generally unknown which parameters are actually available. This paper investigates how to select available parameters for the Crossbred algorithm. As a result, we provide formulae that give an available parameter set and estimate the complexity of the Crossbred algorithm.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: MQ problem MQ challenge Crossbred algorithm
Contact author(s): shuhei nakamura fs71 @ vc ibaraki ac jp
History: 2023-11-19: revised; 2023-11-01: received; See all versions
Short URL: https://ia.cr/2023/1687
License: CC BY

BibTeX

@misc{cryptoeprint:2023/1687,
      author = {Shuhei Nakamura},
      title = {Admissible Parameter Sets and Complexity Estimation of Crossbred Algorithm},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1687},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/1687}},
      url = {https://eprint.iacr.org/2023/1687}
}