Welcome to the resource topic for
**2022/708**

**Title:**

An Estimator for the Hardness of the MQ Problem

**Authors:**
Emanuele Bellini, Rusydi H. Makarim, Carlo Sanna, and Javier Verbel

**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.

**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 .