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 .