🔢 mathematics

Locally-APN Binomials with Low Boomerang Uniformity in Odd Characteristic

本文通过在奇特征域上建立一般性条件，使得 $F_r(x)=x^r+x^{r+\frac{q-1}{2}}$ 的爆破统一性至多为2，从而扩展了关于具有低爆破统一性的局部-APN二项式的近期成果，同时分析了特征为3的域上 $F_3$ 、 $F_{\frac{2q-1}{3}}$ 和 $F_2$ 等具体实例的微分谱与爆破谱。

原作者： Namhun Koo, Soonhak Kwon, Minwoo Ko, Byunguk Kim

发布于 2026-04-28

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Namhun Koo, Soonhak Kwon, Minwoo Ko, Byunguk Kim

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一名守卫一座极高科技金库（即分组密码）的安全员，金库内保护着数字宝藏。为了守护金库安全，你使用一种称为S 盒的特殊锁具机制。该锁具以某种方式扰乱输入数据，使得窃贼极难通过观察输入端的微小变化如何影响输出端来推断出原始密钥。

在密码学领域，数学家使用两种主要工具来衡量这把锁的“混淆”程度：差分均匀性和回旋镖均匀性。

差分均匀性就像测试当你轻轻推门时锁具的反应。如果微小的推动总是导致可预测的巨大摆动，那么这把锁就很脆弱。如果推动引发的是混乱且难以预测的反应，那么这把锁就很坚固。目标是将该数值尽可能保持得低（理想情况下为 1 或 2）。
回旋镖均匀性则是一项更复杂的测试。想象你向锁具投掷回旋镖。你投出它，它击中目标，然后飞回。这项测试检查特定的“投掷与返回”模式是否会揭示弱点。同样，数值越低意味着锁具越坚固。

问题：寻找完美的锁具

多年来，数学家一直在寻找能够制造这些完美锁具的特定数学公式（称为函数）。一个流行的公式家族形式如下：
$F(x) = x^r + x^{r + \text{某项}}$
将 $x^r$ 视为锁具的主引擎，而第二部分则是一个特殊的“调音器”，它根据输入数字是“平方数”还是“非平方数”（一种称为二次特征的属性）来调整锁具的行为。

本文的作者 Namhun Koo 及其团队专注于一种特定的数学世界，称为奇特征（可以将其想象为一个数字行为与我们标准计算机二进制世界截然不同的宇宙）。他们希望找到“引擎”（指数 $r$ ）的特定设置，以使锁具变得极其坚固。

发现：坚固锁具的新规则

该团队发现了一条制造坚固锁具的“黄金法则”。他们发现，如果你选择一个特定的指数 $r$ ，并确保某个方程（与锁具对推动的反应相关）在特定区域内至多有一个解，那么就会发生两件惊人的事情：

差分均匀性很低：锁具是“局部 APN"的。这是一种花哨的说法，意指对于几乎所有可能的推动，锁具的反应都极难预测（具体来说，反应仅限于 2 种可能性）。
回旋镖均匀性很低：锁具也能抵御“回旋镖”攻击，得分至多为 2。

他们证明了该规则适用于一系列特定的指数（例如 $r=3$ 、 $r=2$ 以及其他涉及 3 的幂次的指数）。这就像找到了一把万能钥匙，开启了一整类超安全锁具的大门。

惊喜：修正之前的错误

这是他们故事中最令人兴奋的部分。

过去，其他研究人员研究了一种特定的锁具，其引擎设定为 $r=2$ （一个非常简单的公式）。他们声称，对于足够大的金库，这把锁具的“回旋镖均匀性”为2。他们认为这很好，但并非完美。

本文的作者们进行了更深入的考察，特别是在素数为3的宇宙中（一种特定类型的数学世界）。他们发现，由于素数为 3 时数字运作方式的某种怪癖（具体而言，在该世界中 $1 = -2$ ），之前的研究人员忽略了一个细微的细节。

他们的发现：在这个特定的世界中， $r=2$ 的锁具实际上比之前认为的还要坚固。其回旋镖均匀性为1。

类比：想象之前的研究称某辆汽车的最高时速为 100 英里。这篇新论文说：“实际上，如果在这种特定条件下查看引擎，它的运行速度是 101 英里。”这是一个微小的差异，但在密码学世界中，获得完美的 1 分是一个巨大的成就。

他们具体做了什么

证明了规则：他们从数学上证明，如果“推动”方程的解有限，那么锁具就是坚固的（局部 APN）且能抵御回旋镖攻击。
核查了列表：他们验证了其“表 3"中列出的所有特殊指数都遵循这一规则。
绘制了地形图：对于指数 $r=3$ 和 $r=2q-1/3$ ，他们不仅仅说“它很坚固”，而是绘制了一张完整的地图（称为谱），精确显示了锁具产生 0 个、1 个或 2 个解的次数。这为工程师提供了精确的蓝图。
修正了记录：他们证明了在特征为 3 的情况下， $r=2$ 的锁具实际上是完美的（均匀性为 1），纠正了之前认为其均匀性为 2 的观点。

总结

简而言之，这篇论文是一本构建更好数字锁具的指南。作者们发现了一个可靠的配方，以确保这些锁具能高度抵御两种主要类型的攻击。他们还修正了之前指南中的一处小错误，表明在特定的数学世界中，某一种特定的锁具设计实际上比任何人意识到的都要安全。他们的工作有助于密码学家在未来选择最佳的公式来保护数据。

以下是 Koo 等人论文《奇特征下具有低博梅朗均匀性的局部 APN 二项式》的详细技术总结。

1. 问题陈述

本文探讨了定义在有限域 $\mathbb{F}_q$ （其中 $q = p^n$ 为奇素数幂）上的一类特定函数的密码学性质。研究重点在于形式如下的函数：
$F_r(x) = x^r(1 + \chi(x)) = x^r + x^{r + \frac{q-1}{2}}$
其中 $\chi(x) = x^{\frac{q-1}{2}}$ 为二次特征。

本研究旨在确定这些函数的两个关键安全指标：

差分均匀性（ $\delta_F$ ）： 衡量抵抗差分密码分析的能力。若 $\delta_F = 2$ ，则函数被称为几乎完美非线性（APN）。由于这些函数在许多参数下并非严格全局意义上的 APN，作者研究了它们是否满足局部 APN（即对所有 $b \in \mathbb{F}_q \setminus \mathbb{F}_p$ ，满足 $\delta_F(1, b) \le 2$ ）。
博梅朗均匀性（ $\beta_F$ ）： 衡量抵抗博梅朗攻击的能力。本文旨在确定 $\beta_F \le 2$ 是否成立，并确定完整的博梅朗谱（即博梅朗连通表中解数量的分布）。

具体而言，本文研究了在单项式 $x^r$ 具有低差分均匀性（通常为完美非线性或 APN）且 $\gcd(r, q-1) \mid 2$ 的指数 $r$ 的子类中，这些性质是否成立。

2. 方法论

作者结合了代数数论、特征和分析与有限域上的组合计数方法。

解集的分解： 作者根据 $x$ 和 $x+1$ 的二次特征对域 $\mathbb{F}_q$ 进行划分。定义了集合 $S_{ij} = \{x \in \mathbb{F}_q : \chi(x) = (-1)^i, \chi(x+1) = (-1)^j\}$ ，其中 $i, j \in \{0, 1\}$ 。
差分分析： 为了计算方程 $F_r(x+a) - F_r(x) = b$ 的解数，他们将问题简化为在特定集合 $S_{ij}$ 内分析方程 $(x+1)^r - x^r = b$ 。他们证明了如果该方程在 $S_{00}$ （即 $x$ 和 $x+1$ 均为二次剩余）中至多有一个解，则该函数为局部 APN。
博梅朗分析： 他们分析了定义博梅朗连通表（BCT）的方程组。通过将解空间 $(x, y)$ 分解为集合 $S_{ij} \times S_{kl}$ 的乘积，他们对解的数量进行了界定。
特征和： 作者利用 Weil 界和二次特征的特定性质（例如 $\sum \chi(f(x))$ ）来估计解的数量，并针对特定情况推导出了精确的差分和博梅朗谱。
线性等价： 他们利用引理 2.8 表明某些指数（如 $3^{k+1}/2$ ）与其他指数线性等价，从而使结果得以推广。

3. 主要贡献

A. 一般理论框架

本文建立了一个充分条件，用于判定二项式 $F_r$ 是否为具有低博梅朗均匀性的局部 APN 函数：

条件： 如果 $\gcd(r, q-1) \mid 2$ $g cd (r, q - 1) ∣ 2$ ，且方程 $(x+1)^r - x^r = b$ $(x + 1)^{r} - x^{r} = b$ 对所有 $b \in \mathbb{F}_q^*$ $b \in F_{q}^{*}$ 在 $S_{00}$ $S_{00}$ 中至多有一个解，则：
- $\delta_{F_r} = \frac{q+1}{4}$ （局部 APN）。
- $\beta_{F_r} \le 2$ 。

B. 特定指数的验证

作者验证了上述条件对一系列指数 $r$ 成立（总结于论文表 3 中），包括：

$r = p^k + 1$ （针对奇数 $n$ ）。
$r = \frac{3^{k+1}}{2}$ （广义 Coulter-Matthews 指数）。
$r = 3$ 和 $r = \frac{2q-1}{3}$ （在 $q \equiv 11 \pmod{12}$ 条件下）。
$r = \frac{3^{n+1}-1}{2}$ 和 $r = \frac{3^{n+1}-1}{8}$ （针对 $p=3$ ）。

C. 精确谱的确定

差分谱： 本文推导了当 $q \equiv 11 \pmod{12}$ $q \equiv 11 (mod 12)$ 时， $F_3$ $F_{3}$ 和 $F_{\frac{2q-1}{3}}$ $F_{\frac{2 q - 1}{3}}$ 的精确差分谱。
- 对于 $F_3$ ，谱取决于特征和 $\Gamma$ 。
- 对于 $F_{\frac{2q-1}{3}}$ ，谱被明确计算为 $\{\omega_0 = \frac{q-3}{2}, \omega_1 = \frac{q+5}{4}, \omega_2 = \frac{q-3}{4}, \omega_{\frac{q+1}{4}} = 1\}$ 。
$F_2$ 的博梅朗谱（ $p=3$ ）： 本文提供了 $p=3$ 且 $n$ 为奇数时 $F_2$ 的第一个完整博梅朗谱。

4. 关键结果

局部 APN 性质： 已证明对于表 3 中列出的所有指数，函数 $F_r$ 均为局部 APN，其差分均匀性为 $\frac{q+1}{4}$ 。
博梅朗均匀性界： 对于同一类指数，已证明其博梅朗均匀性至多为 2。
对先前文献的修正（重要发现）：
- 先前的工作（Mesnager 和 Wu，[14]）猜想并证明了对于大 $q$ ， $F_2$ 的博梅朗均匀性为 2。
- 本文推翻了特征 3 下的这一结论。 作者证明，对于 $p=3$ 且 $n$ 为奇数， $F_2$ 的博梅朗均匀性恰好为 1。
- 原因： 在特征 3 中，恒等式 $1 = -2$ 导致先前证明中考虑的某些情况变得不兼容或退化，从而导致了更低的均匀性。
$F_2$ 的显式博梅朗谱（ $p=3$ ）：
该谱由 $\nu_0 = \frac{3q-5+2\Lambda}{4}$ 和 $\nu_1 = \frac{q+1-2\Lambda}{4}$ 给出，其中 $\Lambda = \sum_{x \in \mathbb{F}_q} \chi(x+1)\chi(x^2+1)$ 。

5. 意义

密码设计： 研究结果为在奇特征域上运行的分组密码中的 S 盒提供了新的候选函数。具有低差分和低博梅朗均匀性的函数对于抵抗现代密码分析攻击至关重要。
理论进展： 本文将“局部 APN"函数的理解从研究充分的偶特征情况扩展到了更广泛的范围。它为分析具有特定指数结构的二项式提供了一个统一的框架。
界限的细化： 通过识别一个特定情况（ $p=3$ ），其中博梅朗均匀性从 2 降至 1，本文强调了有限域密码学中针对特征进行具体分析的重要性，纠正了通用特征研究中的假设。
谱的表征： 提供精确的差分和博梅朗谱（而不仅仅是均匀性界限），使得能够更精确地评估这些函数的安全裕度。

总之，本文成功地将局部 APN 性质推广到奇特征下的一类广泛二项式，证明了它们具有低博梅朗均匀性，并对特征 3 下 $F_2$ 的理解做出了关键修正。