International Association
for Cryptologic Research

Multivariate Quadratic polynomial (MQ) problem serve as the basis of

security for potentially post-quantum cryptosystems.

The hardness of solving MQ problem depends on a number of parameters,

most importantly the number of variables and the degree of the

polynomials, as well as the number of equations, the size of the base

field etc. We investigate the relation among these parameters and the

hardness of solving MQ problem, in order to construct hard instances

of MQ problem. These instances are used to create a challenge, which

may be helpful in determining appropriate parameters for multivariate

public key cryptosystems, and stimulate further the research in

solving MQ problem.