Paper 2022/708

An Estimator for the Hardness of the MQ Problem

Emanuele Bellini, Cryptography Research Center, Technology Innovation Institute, UAE
Rusydi H. Makarim, Cryptography Research Center, Technology Innovation Institute, UAE
Carlo Sanna, Department of Mathematical Sciences, Politecnico di Torino, Torino, IT
Javier Verbel

The Multivariate Quadratic ($\mathcal{MQ}$) problem consists in finding the solutions of a given system of $m$ quadratic equations in $n$ unknowns over a finite field, and it is an NP-complete problem of fundamental importance in computer science. In particular, the security of some cryptosystems against the so-called algebraic attacks is usually given by the hardness of this problem. Many algorithms to solve the $\mathcal{MQ}$ problem have been proposed and studied. Estimating precisely the complexity of all these algorithms is crucial to set secure parameters for a cryptosystem. This work collects and presents the most important classical algorithms and the estimates of their computational complexities. Moreover, it describes a software that we wrote and that makes possible to estimate the hardness of a given instance of the $\mathcal{MQ}$ problem.

Note: (2022-07-19): The special case of the Thomae-Wolf strategy (when floor(n/m) divides m) is been removed, and a more accurate formula for Crossbred's time complexity is been added. (2022-07-22): Fixing typo in Crossbred's time complexity.

Available format(s)
Publication info
Published elsewhere. AFRICACRYPT
MQ problem estimator Polynomial solving multivariate cryptography
Contact author(s)
emanuele bellini @ tii ae
rusydi makarim @ tii ae
carlo sanna dev @ gmail com
javier verbel @ tii ae
2022-07-22: last of 2 revisions
2022-06-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Emanuele Bellini and Rusydi H. Makarim and Carlo Sanna and Javier Verbel},
      title = {An Estimator for the Hardness of the MQ Problem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/708},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.