Paper 2022/708
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.
Metadata
- Available format(s)
-
PDF
- 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
- 2022-06-03: received
- See all versions
- Short URL
- https://ia.cr/2022/708
- License
-
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}
}
