Relative Difference sets from Almost Perfect Nonlinear Functions

本文探讨了某些几乎完美非线性（APN）函数与相对差集之间的联系，证明了特定 2 对 1 的 APN 函数的像集构成相对差集，进而通过 Pott 的结果建立了 APN 函数与弯曲函数（bent functions）之间的关联。

要点

这篇论文听起来充满了数学符号和复杂的术语，但如果我们剥去它的外壳，会发现它其实是在讲述一个关于**“寻找完美平衡”和“隐藏规律”**的故事。

想象一下，你正在玩一个极其复杂的数字迷宫游戏。

1. 核心角色：APN 函数（迷宫的守护者）

首先，我们要认识主角：APN 函数（几乎完美非线性函数）。
在密码学（保护你银行卡密码、微信消息安全的技术）的世界里，我们需要一种特殊的“锁”。这种锁必须非常难被破解。

• 比喻：想象 APN 函数是一个超级严格的守门人。
• 它的工作：当有人试图通过改变输入（比如把密码改一个数字）来猜测输出规律时，这个守门人会确保无论怎么改，输出的变化都极其混乱，没有任何明显的模式可循。
• 为什么重要：如果守门人太“好说话”（规律太明显），黑客就能轻易猜出规律（这叫差分攻击）。APN 函数就是那个最难被猜透的守门人，它保证了即使你稍微动一下输入，输出的结果也会像打翻的拼图一样散乱，且这种散乱是“几乎完美”的。

2. 特殊的发现：2-to-1 函数（一对二的魔法）

论文发现了一类特殊的守门人，我们叫它们**"2-to-1 APN 函数”**。

• 比喻：普通的守门人可能是一对一（你进一个门，出来一个人）。但这类特殊的守门人有一个魔法：每两个不同的人，会走进同一个出口。
• 有趣的地方：虽然它们把两个人“合并”了，但它们依然保持着“守门人”那种混乱、难预测的特性。

3. 核心发现：相对差集（完美的拼图）

这篇论文最惊人的发现是：这些"2-to-1 守门人”所生成的出口集合（也就是所有可能的输出结果），竟然构成了一个数学上非常完美的结构，叫做**“相对差集”**。

• 比喻：想象你在一个巨大的广场上（这是所有可能的数字），撒下了一堆特殊的石子（这是函数的输出结果）。
• 相对差集的含义：如果你拿着任意两个石子，计算它们之间的距离（差值），你会发现：
  1. 除了某些特定的“禁区”（ forbidden subgroup，就像广场上的几个特殊区域），广场上的每一个其他位置，都恰好被这些距离覆盖了一次（或固定次数）。
  2. 这就像是一个完美的拼图：没有重叠，没有遗漏，除了那几个特定的禁区。
• 意义：这意味着这些看似混乱的函数输出，背后竟然隐藏着一种极其严谨、对称的几何结构。就像在看似杂乱的噪音中，发现了一首完美的交响乐。

4. 意外的连接：弯曲函数（Bent Functions）

论文还通过一位叫 Pott 的数学家的理论，把这些“守门人”和另一种叫**“弯曲函数”**（Bent Functions）的东西联系了起来。

• 比喻：
  • APN 函数是保护数据的盾牌（防攻击）。
  • 弯曲函数是制造随机性的骰子（用于加密，让数据看起来完全随机）。
• 连接：论文发现，如果你把那个特殊的"2-to-1 守门人”的输出结果拿来用，竟然能直接造出一个完美的随机骰子（弯曲函数）。
• 具体例子：论文证明，某些特定的 APN 函数生成的结构，本质上就是最经典的“二次型”弯曲函数（就像 $x_1x_2 + x_3x_4$ 这种简单的乘法组合）。这就像发现了一个新大陆，原来两个看似完全不同的数学王国（盾牌和骰子），在地下是连通的。

5. 总结与未解之谜

这篇论文讲了什么？
它告诉我们，在数学的迷宫里，有一类特殊的“守门人”（2-to-1 APN 函数），它们不仅防守严密，而且它们留下的足迹（输出集合）竟然能拼成一个完美的几何图案（相对差集），并且这个图案还能直接用来制造完美的随机数（弯曲函数）。

还有什么没解决？（开放问题）
作者最后也诚实地说，虽然发现了这些，但还有很多谜题：

• 是不是所有的"2-to-1 守门人”都能拼出这种完美图案？（答案是否定的，有些不行）。
• 那到底哪些可以？我们怎么一眼认出它们？
• 是不是所有的“完美随机骰子”都能从这些守门人那里找到源头？

一句话总结：
这篇论文就像是在数学的森林里发现了一条隐藏的捷径，它连接了“最坚固的防御”（APN 函数）和“最完美的随机”（弯曲函数），并揭示了它们背后共同拥有的、令人惊叹的对称之美。

技术摘要

这是一份关于论文《Almost Perfect Nonlinear Functions 导出的相对差集》（Relative Difference Sets from Almost Perfect Nonlinear Functions）的详细技术总结。

1. 研究背景与问题 (Problem)

背景：

• APN 函数 (Almost Perfect Nonlinear Functions)： 在有限域 $\mathbb{F}_{2^n}$ 上，APN 函数是指差分均匀性为 2 的函数。它们在密码学中至关重要，特别是作为分组密码中的 S 盒，能有效抵抗差分攻击。
• 相对差集 (Relative Difference Sets, RDS)： 组合数学中的重要结构。一个 $(m, n, k, \lambda)$-相对差集 $R$ 是群 $G$ 的子集，相对于禁止子群 $N$，其元素差能覆盖 $G \setminus N$ 中每个元素恰好 $\lambda$ 次，且不覆盖 $N \setminus \{0\}$ 中的元素。
• 现有联系： 已知某些 2-1 映射（2-to-1 functions）的像集与差集结构有关。例如，作者之前的工作表明 2-1 平面函数（planar functions）的像集是 skew Hadamard 差集或偏差集。

核心问题：

• 是否存在一类特殊的 APN 函数，其**像集（Image Set）**构成相对差集？
• 特别是，已知某些 APN 函数是 2-to-1 的（即每个像点恰好有两个原像），这些函数的像集是否具有相对差集的结构？
• 这种联系能否进一步揭示 APN 函数与 Bent 函数（弯曲函数）之间的关系？

2. 方法论 (Methodology)

本文采用了代数组合学与有限域理论的结合方法：

1. 定义与等价性分析：

   • 利用 APN 函数的定义（差分方程 $f(x+a) - f(x) = b$ 最多有 2 个解）。
   • 利用 EA-等价（Extended Affine）和 CCZ-等价（Carlet-Charpin-Zinoviev）的概念，特别是针对幂函数的 Cyclotomic 等价性，来简化函数的分析。
   • 利用迹函数（Trace function, $\text{Tr}$）的性质处理有限域上的方程。

2. 构造与验证：

   • 选取特定的 2-to-1 APN 函数族。
   • 设 $D$ 为函数的像集。
   • 通过直接计算差集 $x_1 - x_2$（其中 $x_1, x_2 \in D$）的分布情况，验证其是否满足相对差集的定义：
     • 证明禁止子群 $N$ 中的非零元素无法表示为 $D$ 中两元素之差。
     • 计算 $G \setminus N$ 中每个元素被表示为差的次数 $\lambda$。

3. 理论推导：

   • 结合 Pott 的定理：若 $f: K \to N$ 是完美非线性（Perfect Nonlinear）函数，则其图是半正则分裂差集。
   • 在二元域上，完美非线性函数等价于 Bent 函数。通过建立 APN 函数像集与 Bent 函数之间的桥梁，推导 Bent 函数的性质。

3. 主要贡献与结果 (Key Contributions & Results)

A. 三类 2-to-1 APN 函数的像集被证明为相对差集

作者证明了以下三类定义在 $\mathbb{F}_{2^n}$ ($n$ 为奇数) 上的 2-to-1 APN 函数，其像集 $D$ 构成了特定的相对差集：

1. 第一类函数： $f(x) = x^3 + a^{-1}\text{Tr}(a^3x^9)$

   • 条件： $n = 2k+1$ 为奇数，$a \in \mathbb{F}_{2^n}^*$。
   • 结果： 像集 $D$ 是 $(F_{2^n}, +)$ 中相对于子群 $N = \{0, a^{-1}\}$ 的 $(2^{2k}, 2, 2^{2k}, 2^{2k-1})$-相对差集。
   • 推广： 该结论对复合函数 $g(x) + a^{-1}\text{Tr}(a^3g(x)^3)$ 以及线性变换后的函数同样成立。

2. 第二类函数： $k(x) = x^6 + \alpha x^3 + \gamma \text{Tr}(\alpha^{-3}x^9 + \beta x^3)$

   • 条件： $n$ 为奇数，$\alpha, \beta, \gamma$ 非零，$\gamma \notin \{x^2+\alpha x\}$，且 $\text{Tr}(\beta \alpha) = 1$。
   • 结果： 该函数是 2-to-1 APN 函数，其像集是相对于子群 $N = \{0, \gamma\}$ 的 $(2^{2k}, 2, 2^{2k}, 2^{2k-1})$-相对差集。
   • 联系： 该函数实际上是第一类函数经过线性变换和置换后的形式。

3. 第三类函数： $f(x) = x^{2^k-1} + x^{2^k}$

   • 条件： $k \ge 2$，定义域为 $\mathbb{F}_{2^{2k-1}}$。
   • 结果： 该函数是 2-to-1 APN 函数，其像集是相对于子群 $N = \{0, 1\}$ 的 $(2^{2k-2}, 2, 2^{2k-2}, 2^{2k-3})$-相对差集。

重要反例：
作者指出，并非所有 2-to-1 APN 函数的像集都是相对差集。例如，$f(x) = x^3 + x^4$ 在 $n$ 为奇数时是 2-to-1 APN 函数，但其像集并不总是相对差集。这表明该性质具有特定的结构性，而非普遍存在。

B. 建立 APN 函数与 Bent 函数的联系

• 利用 Pott 的定理（2004），将 APN 函数像集的相对差集性质转化为 Bent 函数的存在性。
• 定理 3.2： 对于第一类函数 $h(x) = x + a^{-1}\text{Tr}(a^3x^3)$，其导出的 Bent 函数在仿射等价意义下等价于标准的二次 Bent 函数：
  $$x_1x_2 \oplus x_3x_4 \oplus \cdots \oplus x_{n-2}x_{n-1} \oplus \epsilon$$
  这证明了该类 APN 函数生成的 Bent 函数属于已知的二次 Bent 函数类。
• 对于第三类函数 $x^{2^k-1} + x^{2^k}$，虽然尚未严格证明其对应的 Bent 函数形式，但小规模计算表明其对应的 Bent 函数也是二次的。

4. 意义与影响 (Significance)

1. 连接密码学与组合设计： 本文在 APN 函数（密码学核心组件）和相对差集（组合设计核心结构）之间建立了具体的代数联系。这不仅丰富了 APN 函数的理论分类，也为构造新的相对差集提供了新的代数方法。
2. 深化对 2-to-1 映射的理解： 揭示了 2-to-1 APN 函数在特定条件下具有极强的代数结构（像集为差集），这有助于理解为何某些 APN 函数具有优异的差分特性。
3. Bent 函数的新视角： 通过 Pott 的定理，将 APN 函数的像集性质与 Bent 函数联系起来。虽然目前发现的对应 Bent 函数多为已知的二次型，但这为寻找新的 Bent 函数或理解 Bent 函数的来源提供了新的路径。
4. 开放性问题： 论文提出了关键问题，即“哪些 APN 函数能导出相对差集？”以及“是否所有 APN 函数都等价于能导出相对差集的函数？”。这些问题为未来的研究指明了方向。

总结

Zeying Wang 的这篇论文通过严格的代数推导，证明了特定族类的 2-to-1 APN 函数的像集构成了相对差集。这一发现不仅扩展了相对差集的构造方法，还通过 Pott 的定理揭示了这些 APN 函数与二次 Bent 函数之间的深刻联系，为有限域上的函数理论、组合设计及密码学设计提供了重要的理论支撑。