Binary quadratic systems with one solution outnumber those with none
A Note on Binary Quadratic Systems and their relation to complexity theory
Information TheoryComputational ComplexityCryptography and Security
Summary
Finding solutions to certain sets of equations with variables that can only be 0 or 1 is a very hard problem in computer science. The authors studied systems of such equations that either have no solutions or exactly one solution. They proved that for every size of the system, there are always more systems with exactly one solution than those with none, and they provided precise bounds on their ratio. Their proof uses ideas from matroid theory and error-correcting codes. This helps better understand the complexity of these problems, which is important for cryptography.
What this means in practice
- •For post-quantum cryptography engineers: Better understanding of solution distributions in binary quadratic systems aids secure cryptosystem design assumptions.
- •For error-correcting code designers: Provides analysis linking Reed–Muller code properties to polynomial system solutions, informing code structure insights.
A theory result. No direct application yet.
Authors
Gabriele Radici, Massimiliano Sala
Abstract
Deciding whether a system of multivariate quadratic equations over $\mathbb F_2$ has a solution is a classical NP-complete problem, and remains so for square systems, with as many equations as variables. The hardness of this problem is one of the cornerstones of nowadays post-quantum cryptography. Let $\MQ_0(n)$ and $\MQ_1(n)$ denote the sets of square quadratic systems in $n$ variables having respectively no solutions and exactly one solution. $\cup_{n\geq 2} \MQ_0(n)$ is a coNP-complete language, while $\cup_{n\geq 2} \MQ_1(n)$ lies in DP. It is known that $\lim_{n\to \infty} |\MQ_1(n)|/|\MQ_0(n)|=1$. Here we prove the explicit finite-$n$ bounds \[ |\MQ_0(n)|<|\MQ_1(n)| \le \left(1+\frac{1}{2^n-1}\right)|\MQ_0(n)|, \] More generally, let $Q_d$ be the space of polynomial functions $(\FF_2)^n\to\mathbb F_2$ of degree at most $d$, and let $α_k$ count square systems in $(Q_d)^n$ having exactly $k$ solutions. Then \[ α_0<α_1 \le \left(1+\frac{1}{2^n-1}\right)α_0\,, \qquad 2\le d\le n \,. \] The proof combines matroid and coding-theoretic methods. We interpret $(\FF_2)^n$ as the ground set of the evaluation matroid of $Q_d$, express $α_0$ and $α_1$ through characteristic polynomials, and use a Whitney-type sign-reversing involution to show that the only terms that can push $α_1-α_0$ below $α_1/2^n$ come from the elements of a matroid port. These are identified with minimal-support words of the Reed--Muller code $\RM(n-d-1,n)=\RM(d,n)^\perp$; the required estimate then follows from the MacWilliams identity, the minimum-distance bound $2^{d+1}$, and the even-weight structure of the code.