multivariatequadratic

Multivariate quadratic refers to polynomials in several variables whose total degree is at most two. In mathematics and computer algebra, these functions are studied for their algebraic structure and computational properties. When defined over a field F, an MQ polynomial in variables x1, ..., xn can be written in general form as a sum of quadratic terms, a linear term, and a constant: f(x) = sum_{i≤j} a_{ij} x_i x_j + sum_i b_i x_i + c, with coefficients a_{ij}, b_i, c in F. Equivalently, the quadratic part can be expressed as x^T A x where A is a symmetric matrix, together with a linear part b^T x and a constant c.

The multivariate quadratic problem (MQ problem) considers systems of several such polynomials. Given m equations in n variables over a field, each equation being quadratic, the task is to find a solution x in F^n that satisfies all equations, or to determine that none exists. The MQ problem is known to be computationally hard in general; over finite fields it is NP-hard, and in the boolean case (GF(2)) the decision version is NP-complete. Hardness depends on the number of variables, the number of equations, and the particular structure of the system. Algorithms such as Gröbner bases and linearization methods (XL) are used to attack MQ systems, with practical performance varying widely by instance.

MQ systems have significant applications in cryptography, where they form the basis of several multivariate public-key cryptosystems. Notable examples include the Hidden Field Equations (HFE) scheme and the Unbalanced Oil and Vinegar (UOV) scheme. These systems rely on the presumed hardness of solving MQ equations, even against quantum attacks, making MQ a central area of study in post-quantum cryptography and computational algebra.