Paper 2024/758

Admissible Parameters for the Crossbred Algorithm and Semi-regular Sequences over Finite Fields

John Baena, Universidad Nacional de Colombia
Daniel Cabarcas, Universidad Nacional de Colombia
Sharwan K. Tiwari, Technology Innovation Institute
Javier Verbel, Technology Innovation Institute
Luis Villota, Universidad Nacional de Colombia
Abstract

Multivariate public key cryptography (MPKC) is one of the most promising alternatives to build quantum-resistant signature schemes, as evidenced in NIST's call for additional post-quantum signature schemes. The main assumption in MPKC is the hardness of the Multivariate Quadratic (MQ) problem, which seeks for a common root to a system of quadratic polynomials over a finite field. Although the Crossbred algorithm is among the most efficient algorithm to solve MQ over small fields, its complexity analysis stands on shaky ground. In particular, it is not clear for what parameters it works and under what assumptions. In this work, we provide a rigorous analysis of the Crossbred algorithm over any finite field. We provide a complete explanation of the series of admissible parameters proposed in previous literature and explicitly state the regularity assumptions required for its validity. Moreover, we show that the series does not tell the whole story, hence we propose an additional condition for Crossbred to work. Additionally, we define and characterize a notion of regularity for systems over a small field, which is one of the main building blocks in the series of admissible parameters.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Admissible parameterCrossbredSemi-regularMQ ProblemPost-QuantumCryptography
Contact author(s)
jbbaena @ unal edu co
dcabarc @ unal edu co
sharwan tiwari @ tii ae
javier verbel @ tii ae
ldvillotav @ unal edu co
History
2024-05-20: approved
2024-05-17: received
See all versions
Short URL
https://ia.cr/2024/758
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/758,
      author = {John Baena and Daniel Cabarcas and Sharwan K. Tiwari and Javier Verbel and Luis Villota},
      title = {Admissible Parameters for the Crossbred Algorithm and Semi-regular Sequences over Finite Fields},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/758},
      year = {2024},
      url = {https://eprint.iacr.org/2024/758}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.