技术摘要：同次数方程组求解的复杂度

问题陈述

许多加密方案（特别是多变量密码学和后量子设置中的方案）的安全性依赖于在有限域上求解多元多项式方程组的计算难度。通过 Gröbner 基方法求解此类系统的复杂度主要由正则次数（degree of regularity, $d_{reg}$）和求解次数（solving degree）决定。虽然正则次数为 Gröbed 基计算提供了一个复杂度的上界，但在处理具有密码学规模的系统时，计算或估计该值通常非常困难。

通常的做法依赖于一个启发式假设，即系统是半正则（semiregular，或称密码学半正则）的，这可以得出正则次数的显式公式。然而，这一假设并不总是成立；在某些参数选择和域中，不存在半正则序列。因此，需要经过证明的、非启发式的正则次数和求解次数上界，且这些上界应适用于正则次数有限的系统，而不依赖于半正则性假设。

方法论

作者使用交换代数工具来解决这一问题，特别关注那些其最高次项部分生成的理想包含 $n$ 个给定次数 $D$ 的正则序列（regular sequence）的系统。

1. 框架： 本文考虑一个由 $m$ 个 $n$ 元多项式组成的系统 $F = \{f_1, \dots, f_m\}$，其定义在域 $F$ 上。分析假设 $f_1^{top}, \dots, f_m^{top}$（最高次项部分）是线性无关的，并且该系统在次数 $D$ 下是正则的（即由最高次项部分生成的理想包含 $n$ 个次数为 $D$ 的正则序列）。
2. 归约为 LPP 理想： 为了界定 Castelnuovo-Mumford 正则性（当其有限时等于正则次数），作者利用了 Eisenbud-Green-Harris (EGH) 猜想。该猜想认为，在包含特定次数的正则序列的所有齐次理想中，Lex-Plus-Powers (LPP) 理想具有最大的正则性。
3. 组合分析： 作者构造了与给定参数（$n, m, D$）相关的特定 LPP 理想。通过分析这些理想在字典序下的结构，他们确定了 LPP 理想的正则性，该正则性作为原系统正则性的上界（基于 EGH 猜想）。
4. 域方程： 该方法被扩展到增加了域方程（$x_i^q - x_i$）的系统，这对于当方程次数 $D$ 大于或等于域大小 $q$ 时的有限域 $\mathbb{F}_q$ 系统至关重要。

核心贡献与结果

1. 关于次数 $D$ 下正则系统的上界（不含域方程）

定理 23 为由 $m$ 个 $n$ 元 $D$ 次方程组成的系统提供了正则次数的精确上界，前提是该系统在次数 $D$ 下是正则的。

• 该界限取决于方程数量（$m$）、变量数量（$n$）和次数（$D$）。
• 公式涉及识别唯一的整数 $k$ 和 $t$，使得 $m-n$ 落在由组合和（$\sigma_{k,t}$）定义的特定区间内。
• 所得界限为：$d_{reg}(F) \le (D - t) + (n - k)(D - 1)$。
• 该界限对于所有 $m, n, D$ 的取值都是精确的（sharp），并由最高次项部分形成特定 LPP 理想的系统所达到。

推论 27 将此转化为变异算法（mutant algorithms）的求解次数上界：
$$\text{solv. deg}_m(F) \le D - t + 1 + (n - k)(D - 1)$$

2. 带有域方程的系统上界

论文讨论了增加域方程的情况，这在 $D \ge q$ 时对于有限域系统是必不可少的。

• 命题 31： 对于极度超定系统（即 $m$ 超过了模去域方程后的多项式空间维度），正则次数恰好为 $D$。
• 定理 33： 对于满足 $q \le D \le n(q-1)$ 且最高次项部分在模去域方程后线性无关的系统，作者提供了正则次数的上界。
  • 该界限是通过分析在次数 $D$ 的单项式关于 $(x_1^q, \dots, x_n^q)$ 的字典序中的第 $m$ 个单项式的位置而得出的。
  • 界限用 $B = q - t + (n - k)(q - 1)$ 表示，其中 $k$ 和 $t$ 由包含 $m$ 的区间决定。
  • 根据 $m, D, t$ 的具体条件，界限为 $B$ 或 $B-1$。

推论 34 将这些结果专门用于二进制系统（$q=2$），为 $\mathbb{F}_2$ 上 $D$ 次系统的正则次数和求解次数提供了简化的公式。

3. 对特定方案的应用

作者将这些界限应用于具体的密码方案：

• 三次简单矩阵（Cubic Simple Matrix）： 他们导出了一个经过证明的界限 $d_{reg} \le 2n - 1$，这是该系统首个经过证明的界限，与之前的启发式估计形成对比。
• 非平衡油醋方案（Unbalanced Oil and Vinegar, UOV）： 界限被应用于 $\mathbb{F}_2$ 上的 UOV 系统，展示了在包含域方程时正则次数的行为。

意义与主张

本文的主旨在于提供求解多项式系统的经过证明的、非启发式的界限。

• 可靠性： 不同于基于半正则性假设的估计（该假设可能在某些参数下失效），这些界限适用于任何正则次数有限且在给定次数下是正则的系统。

• 通用性： 结果适用于任意域上的系统，并涵盖了包含和不包含域方程两种情况。
  上述研究旨在为广泛的相关多项式系统建立现有 Gröbner 基方法（包括标准和变异方法）的理论极限，而非提出新的算法或实验实现。

• 精确性： 这些界限被描述为“精确的”（sharp），这意味着它们可以由特定系统（LPP 理想）达到，从而为安全性分析提供现实的最坏情况估计。

• 局限性： 作者明确承认，与在半正则性启发式下获得的界限相比，他们的界限通常不够紧凑（即数值更高）。然而，他们认为为了避免使用未经证明的假设（特别是在不存在半正则序列的情况下），这种权衡是必要的。