[Resource Topic] 2022/708: An Estimator for the Hardness of the MQ Problem

Welcome to the resource topic for 2022/708

An Estimator for the Hardness of the MQ Problem

Authors: Emanuele Bellini, Rusydi H. Makarim, Carlo Sanna, and 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.

ePrint: https://eprint.iacr.org/2022/708

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .