Quadratic APN Functions in Dimension 8 via Gröbner Basis Search in a Self-Equivalence Subspace

技术摘要：通过自等价子空间中的 Gröbner 基搜索探索 8 维二次 APN 函数

问题陈述
在 $\mathbb{F}_{2^n}$ 上对几乎完美非线性（APN）函数进行基于 CCZ 等价性的分类是密码学中的一个核心问题，特别是对于 $n=8$ 的情况。虽然对于 $n \leq 6$ 的分类已经完成，但对于 $n=8$ 的分类仍是不完整的。二次 APN 函数的搜索空间极其庞大（可能的系数向量为 $2^{224}$），由于估计的 APN 密度约为 $2^{-n}$，全局随机搜索是不可行的。之前的系统性尝试，例如 Beierle, Brinkmann 和 Leander (BBL2021) 的递归树搜索，探索了由自等价约束定义的结构化代数子空间。具体而言，BBL2021 报告称，在与阶数为 5 的线性自同构 $A$（类指数 22）相关的 40 维自等价子空间 $V_A$ 中未发现 APN 函数。本文研究了该子空间是真的不包含 APN 函数，还是之前的搜索方法未能定位到它们。

方法论
作者提出了一个结合随机采样与代数枚举的两阶段计算流水线，旨在比之前的树搜索更有效地探索 $V_A$。

1. 第一阶段：通过 RREF 参数化进行随机采样
   作者构建了一个显式的简化行阶梯形（RREF）参数化，用于表示 40 维子空间 $V_A = \{F : F \circ A = A \circ F\}$。这使得搜索空间从 $2^{224}$ 缩减至 $2^{40}$。在该子空间内，APN 函数的经验密度约为 $10^{-4}$（大约每 11,000 个随机样本中存在 1 个 APN 函数），这使得有针对性的采样变得可行。作者通过随机采样来识别“APN 中心”（属于 $V_A$ 的 APN 函数）。

2. 第二阶段：Gröbner 基切片计算
   对于第一阶段中找到的每个 APN 中心，作者定义了一个经过该中心的 24 维仿射超平面（一个“NL=4 切片”）。这是通过将 224 个代数正规形式（ANF）系数中的 200 个（具体为对应于索引 $p \leq 4$ 的对的系数）固定为中心函数的值，从而留下 24 个未知系数来实现的。
   APN 条件（针对 255 个非零差分）被编码为一个布尔环上的多项式方程组。作者使用 Magma 计算代数系统，计算该系统的 Gröbner 基。

• 如果系统不可行，则该切片内不包含其他 AP 函数。
• 如果系统有解，Gröbner 基枚举将找到该特定 24 维超平面内的所有 APN 函数。
  至关重要的是，虽然中心函数保证在 $V_A$ 内，但通过 Gröbner 基步骤找到的解并不受限于 $V_A$；它们可能位于自等价子空间之外。

3. 分类与验证
   作者使用正交导数不变性 $\sigma(F)$ 对发现的函数进行分类，该不变性已被证明是二次 APN 函数的完整 CCZ 不变性（根据 Yoshiara 定理及 Canteaut 等人的结果）。作者将这些特征签名与三个主要数据库进行流式比较：BBL2021 pre-2020 汇编、Beierle 等人 2025 年的数据库（包含约 380 万个函数）以及经典的 Gold 函数族。

关键结果
作者在 428 个不同的 24 维切片上执行了该流水线（占 $V_A$ 总共 $2^{16}$ 个可能切片的 0.65%）。

• 发现新类别： 搜索发现了 566 个独特的二次 APN 函数，分布在六个 CCZ 等价类中。
  • 四个新类别 (A, B, C, D)： 这 500 个函数（类别 A 有 362 个，B 有 72 个，C 有 36 个，D 有 30 个）在 Beierle 2025 数据库、BBL2021 pre-2020 数据库或经典 Gold 系列中均不存在。
  • 两个已知类别 (E, F)： 这些对应于 Gold 函数 $x^3$ 和 $x^9$（及其 Frobenius 轨道），作为验证流水线的对照组。
• 结构性发现：
  • 子空间成员身份： 成员身份测试（$F \circ A = A \circ F$）显示，类别 A、E 和 F 完全位于 $V_A$ 内。然而，类别 B、C 和 D 完全位于 $V_A$ 之外。
  • “门户”现象： 位于外部新类别的 138 个函数（B, C, D）仅在以位于 $V_A$ 内的 Gold 函数（类别 E 和 F）为中心的切片中被发现。以类别 A 函数为中心的切片未产生任何 $V_A$ 之外的邻居。
  • 替代种子失效： 使用来自 Beierle 2025 数据库的 532 个位于 $V_A$ 之外的 AP 函数作为切片中心进行的对比实验结果显示，未发现 APN 邻居。这表明通过 Gröbner 基切片发现新类别的“门户”能力是特定于自等价子空间的，而非所有 AP 函数的通用属性。

意义与主张
本文声称对 APN 函数分类领域做出了以下几项重要贡献：

1. 修正先前结果： 作者证明了此前被 BBL2021 报告为不包含 APN 函数的自等价子空间 $V_A$（类指数 22），实际上包含了至少四个二次 APN 函数的 CCZ 类。BBL2021 树搜索的失败归因于其分支剪枝策略，该策略可能会消除该结构化子空间中的有效解，而 Gröbner 基方法则能对每个切片进行完整枚举。
2. 发现新函数： 本文通过正交导数不变性提供了严格证明，证明了 $n=8$ 时存在四个新的二次 APN 函数 CCZ 类，且这些类不同于已知的 $\approx 380$ 万个函数中的任何一个。
3. 方法论创新： 本文引入了一种“GB 导航”机制。作者认为，虽然全局搜索是不可能的，但可以通过利用具有较高 APN 密度的结构化子空间来寻找“种子”函数。随后，Gröbner 基步骤充当局部枚举器，能够跨越子空间边界以寻找新的类别。作者强调，这种机制并非通用的；它依赖于自等价子空间的特定代数结构，这一点从非子空间函数无法作为高效种子的实验结果中得到了证实。
4. 正交导数的完备性： 本研究强化了正交导数签名作为二次函数精确 CCZ 不变性的效用，从而实现了无需穷举两两测试的严格分类。

作者总结道，他们的方法为通过探索其他 BBL2021 类指数并利用 Gröbner 基切片技术来导航 APN 图谱，提供了一个系统性的程序，以扩展二次 APN 函数的分类。