本文研究二元域 F2 上多元二次方程系统(MQ 系统)的解计数及其与复杂度理论的关系。判定一个平方二次系统(方程数等于变量数)是否有解是经典的 NP 完全问题,其困难性是构造后量子密码方案的基石。令 MQ_0(n) 和 MQ_1(n) 分别表示 n 个变量、n 个方程且无解或恰有一解的平方二次系统集合。已知这两个集合对应语言的复杂性不同,且当 n 趋于无穷大时,二者规模之比趋近于 1。本文给出了这一极限现象的显式有限 n 界:对于所有 n,有 |MQ_0(n)| < |MQ_1(n)| ≤ (1 + 1/(2^n - 1)) |MQ_0(n)|。更一般地,考虑所有次数不超过 d 的 n 元多项式函数构成的空间 Q_d,平方系统由 Q_d^n 中的 n 个函数构成。定义 α_k 为恰好有 k 个平方根的此类系统数量,则对于任意 2 ≤ d ≤ n,同样成立 α_0 < α_1 ≤ (1 + 1/(2^n - 1)) α_0。证明方法融合了拟阵论与编码理论:将 (F2)^n 视为 Q_d 的评价拟阵的底层集,α_0 和 α_1 可表示为拟阵的特征多项式;随后利用 Whitney 型反号对合证明,α_1 - α_0 若低于 α_1/2^n,则唯一导致偏差的项来自拟阵的端口(port)元素。这些元素可识别为 Reed-Muller 码 RM(n-d-1,n)=RM(d,n)^⊥ 中的最小支撑权字。最终估计依赖于 MacWilliams 恒等式、码的最小距离界 2^{d+1} 以及偶权重结构。该结果严格证明了 MQ_1 系统的数量始终略多于 MQ_0 系统,但差距不超过一个指数小的因子,这对深入理解 MQ 问题在密码学中的困难性具有重要意义,也为拟阵与编码理论的交叉应用提供了一个新的范例。
💡 推荐理由: 多变量二次方程组的困难性是后量子密码(多变量密码学)安全性的核心假设。该论文严格刻画了无解与唯一解系统数量的差距,为评估此类方案的抗攻击能力提供了理论支撑,有助于安全研究人员更准确地把握MQ问题的复杂度边界。
🎯 建议动作: 研究跟进