Paper 2026/2022

A Partial Injection from Unsatisfiable to Uniquely Satisfiable Quadratic Systems

Abstract

Let $\mathrm{MQ}_0(n)$ and $\mathrm{MQ}_1(n)$ be the sets of square systems of $n$ quadratic equations in $n$ variables over $\mathbb{F}_2$ having, respectively, no solution and exactly one solution, and write $\alpha_0=|\mathrm{MQ}_0(n)|$, $\alpha_1=|\mathrm{MQ}_1(n)|$. It is known that $\alpha_0<\alpha_1$, so injections $\mathrm{MQ}_0(n)\hookrightarrow\mathrm{MQ}_1(n)$ exist; the proof is a counting argument and produces no map. We exhibit a partial injection $\tau$, in the following sense. The map $\tau$ adds to a system a single correction supported on an affine flat of codimension two through a point read off by a three-point decoder; it is computable in $\Theta(n^3)$ bit operations from the dense coefficient representation, with no precomputation and no advice. We prove that there is a subset $\mathcal{D}\subseteq\mathrm{MQ}_0(n)$ with $|\mathcal{D}|/|\mathrm{MQ}_0(n)|>0.745$, uniformly in $n\ge3$, on which $\tau$ is injective into $\mathrm{MQ}_1(n)$. We then show that inverting $\tau$ is \emph{equivalent} to locating a zero of the image system --- the solvable case of the multivariate quadratic problem, and its one-solution case on the uniquely solvable part of the image --- and that $\tau$ is randomly self-reducible on each orbit of its symmetry group. Under the standard assumption that solvable $\mathrm{MQ}$ is hard on average --- the planted-$\mathrm{MQ}$ assumption of $\mathrm{MQ}$-based identification and signature schemes --- $\tau$ is therefore a one-way function, injective on $\mathcal{D}$, explicit and randomly self-reducible on each orbit, between two sets which are, as languages, complexity-theoretically far apart. We also show that the associated flat-collision problem is NP-complete.