Abstract

In a joint study with Gabriele Radici we have examined square MQ systems, that is, polynomial systems in n variables, n equations, each equation with degree 0,1 or 2.

Those with zero solutions form a coNP-complete language MQ0, those with one form a language MQ1 in DP (equivalent to EXACTSAT and so conjectured to be DP-complete), those with one or more form an NP-complete language. It's known that the ratio MQ1(n)/MQ0(n) goes to 1 with n growing and it's also known that it's possible to injectively embed MQ0 into MQ1 BUT with different lengths. We prove that in effect MQ1(n) is always larger than MQ0(n) for all n, so a formal injective function exists WITHOUT changing the string size. Moreover, we explicitly present a map from MQ0(n) to MQ1(n) that it's an injection on 3/4 of MQ0(n). With that, we identify a sequence of coNP-complete sublanguages that are embedded with constant-size inside MQ1. Finally, we derive some considerations in complexity theory and postquantum cryptography. We acknowledge some assistance in the proofs by LLM's Fable and chatGPT. These two preprints contain some of our initial results:

https://arxiv.org/abs/2609.07769

https://eprint.iacr.org/2026/2022

Bio

Massimiliano Sala, Professeur à l’Université de Trento (Italie) et directeur de De Cifris.