On APN Exponents and the Differential and Boomerang Properties of Binomials in Characteristic 3

技术摘要：关于特征 3 下二项式的 APN 指数及其差分与回飞镖性质

问题陈述
本文研究了有限域 $\mathbb{F}_{3^n}$ 上形式为 $F_r(x) = x^r(1 + \chi(x))$ 的二项式函数的密码学性质，其中 $\chi(x)$ 为二次特征。虽然差分均匀性是抵抗差分攻击的标准度量，但它未能完全捕捉对回飞镖攻击的抵抗力。为此引入了回飞镖均匀性（$\beta_F$）的概念。先前的研究 [9] 表明，对于某些指数 $r$，函数 $F_r$ 表现出较低的差分均匀性，且回飞镖均匀性有界于 2。然而，经验观察表明，在特征 3 中，出现极低回飞镖均匀性（具体为 0 或 1）的情况比其他特征更为频繁。本文旨在系统分析这些现象，识别产生回飞镖均匀性 0 或 1 的具体指数 $r$，并为这些类提供严格的证明。

方法论
作者采用了理论分析与计算验证相结合的方法：

1. 理论框架：本研究建立在“局部-PN"和“局部-APN"函数的概念之上。通过分析微分方程 $(x+1)^r - x^r = b$ 及其关联的回飞镖系统，作者推导出了差分谱和回飞镖谱可被明确确定的条件。
2. APN 分类：本文对源自 Zha 和 Wang [23] 构造的几乎完美非线性（APN）幂函数进行了系统参数化。这涉及求解丢番图条件 $(3m+1)r - 2 = k(3^n-1)$ 以生成显式的指数族。
3. 特征和与谱分析：为了确定特定类（特别是 $r = 3^n - 3$）的回飞镖谱，作者评估了涉及二次特征和多项式根的特征和。
4. 计算搜索：使用 SageMath 对小值 $n$（直至 $n=13$）进行了穷举搜索，以识别产生回飞镖均匀性 0 或 1 的指数。这些结果与推导出的理论族进行了交叉验证。

主要贡献与结果

• APN 指数的参数化：作者提出了源自 [23] 框架的 APN 指数的显式参数化（命题 3.3）。他们证明，对于 $n \le 13$，该广义构造涵盖了特征 3 中所有已知但未在标准表 [2] 中列出的 APN 幂函数。这包括恢复已知类（例如 $r = 3^{(n+1)/2} - 1$）并识别新的孤立实例。
• 两类回飞镖均匀性为 0 的函数：本文严格证明了两类特定的二项式 $F_r$ 具有最小的可能回飞镖均匀性 0：
  1. 源自 [23] 中 APN 构造的指数 $r$（满足条件 $(3m+1)r - 2 = k(3^n-1)$）。
  2. 指数 $r = 2 \cdot 3^{(n-1)/2} + 1$。
     对于这两类，作者证明了 $F_r$ 是局部-PN 的，并推导了它们的差分谱。
• $r = 3^n - 3$ 的分析：本文分析了指数为 $r = 3^n - 3$ 的二项式。证明表明，对于奇数 $n \ge 5$，该函数是局部-APN 的，且回飞镖均匀性为 1。作者通过评估特定的特征和，完全确定了其回飞镖谱，提供了产生 $\beta_{F_r}(1, b) = 0$ 和 $1$的$b$ 值数量的显式公式。
• 数值分类：通过对 $n \le 13$ 的穷举搜索，作者编制了产生回飞镖均匀性 0 和 1 的指数表。他们观察到，对于 $n \le 9$，成为局部-PN 的条件似乎既是回飞镖均匀性为 0 的必要条件也是充分条件，即使没有使用先前理论界限中严格的 $\gcd(r, 3^n-1) \in \{1, 2\}$ 假设。

意义
本文阐明并扩展了关于特征 3 下二项式密码学性质的现有研究。其主要意义在于：

1. 系统表征：提供了一个统一的框架，解释了特征 3 中某些二项式为何能达到回飞镖均匀性 0 或 1，将这些性质直接与特定的 APN 指数构造联系起来。
2. 界限扩展：证明了回飞镖均匀性为 2 的一般界限（在 [9] 中确立）对于特征 3 中的特定无限族可以严格改进为 0 或 1。
3. APN 分类的完备性：表明源自 [23] 的 APN 指数参数化涵盖了小 $n$ 下特征 3 中所有已知的 APN 幂函数，暗示了这些函数具有全面的结构。
4. 经验验证：数值结果支持了理论发现，并突出了局部-PN 性质与回飞镖均匀性 0 之间的强相关性，将此关系作为一个潜在的未来严格证明领域。

作者得出结论，虽然他们已经识别出具有最优回飞镖性质的无限族和孤立情况，但局部-PN 性质与回飞镖均匀性 0 之间的精确等价关系仍然是一个未解决的问题，而将回飞镖均匀性为 1 的孤立情况扩展为无限族是未来研究的一个方向。