### An Estimator for the Hardness of the MQ Problem

##### Abstract

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
Keywords
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
History
2022-07-22: last of 2 revisions
See all versions
Short URL
https://ia.cr/2022/708

CC BY

BibTeX

@misc{cryptoeprint:2022/708,
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{https://eprint.iacr.org/2022/708}},
url = {https://eprint.iacr.org/2022/708}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.