Paper 2026/733

Explicit Bounds on the Existence Probability of Random Multivariate Quadratic Systems over Finite Fields

Abstract

The security of multivariate public-key cryptography, a major approach to post-quantum cryptography, is based on the computational hardness of solving systems of multivariate quadratic equations over finite fields (the MQ problem). The MQ problem consists of solving a system of quadratic equations over a finite field of size $q$, with $n$ variables and $m$ polynomials. The existence probability of solutions to the MQ problem plays a central role in analyzing the security of multivariate cryptography. However, explicit bounds for fixed parameters $(q,n,m)$ have not been sufficiently studied. In this work, we evaluate the existence probability for randomly generated MQ systems with fixed parameters by analyzing the coefficient space arising from the MQ system. Using the inclusion--exclusion principle, we obtain a lower bound (approximately $0.625$) and an upper bound (approximately $0.667$) on the existence probability, focusing on the case $m=n$. We also derive upper and lower bounds on the probability that the number of solutions is exactly one in the case $m=n$. Finally, we analyze the existence probability of solutions to the MQ problem in the case $m \neq n$.