Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers

该论文证明了有限域上几乎所有向量函数的扩展仿射稳定子均为平凡群，从而确立了扩展仿射等价类的渐近数量等于函数总数除以扩展仿射群大小的精确公式，并表明随机采样策略在密码原语设计中是有效的。

要点

这篇论文探讨了一个关于密码学核心组件（S 盒）的有趣数学问题。为了让你轻松理解，我们可以把这篇论文想象成在研究一个巨大的“乐高积木宇宙”。

1. 背景：我们在玩什么游戏？

想象你正在设计一种超级安全的密码锁（比如 AES 加密算法）。这种锁的核心部件叫做S 盒（S-box）。你可以把 S 盒想象成一个复杂的“变形机器”：

• 你输入一串数字（比如 8 位二进制数），它经过一番复杂的变换，吐出一串新的数字。
• 为了安全，这个变换必须非常“混乱”，让黑客猜不透规律。

在数学上，这些“变形机器”就是向量布尔函数。

2. 核心问题：有多少种“独特”的机器？

密码学家想知道：在这个巨大的宇宙里，到底有多少种本质上不同的 S 盒？

这里有一个陷阱：有些机器虽然看起来长得不一样，但它们其实是“换汤不换药”。

• 例子：如果你把机器的输入口换个顺序，或者把输出口换个颜色，机器内部的核心逻辑其实没变。
• 在数学上，这叫做EA 等价（Extended-Affine Equivalence）。如果两个函数可以通过这种简单的“换顺序”或“加常数”互相转换，我们就认为它们是同一类（同一个等价类）。

关键问题：

1. 分类问题：如果我们把所有“换汤不换药”的机器归为一类，到底有多少个真正的独特类别？
2. 随机搜索问题：如果我们想找一个特别好的 S 盒，能不能随机生成？会不会运气不好，随机生成了好几个，结果发现它们其实都是“同一类”的（撞车了），导致我们白忙一场？

3. 论文的发现：绝大多数机器都是“独一无二”的

这篇论文给出了一个惊人的结论：在无限大的函数宇宙中，几乎 100% 的函数都是“独一无二”的，它们没有“双胞胎”或“替身”。

为了理解这一点，我们需要引入一个概念：稳定子（Stabilizer）。

创意比喻：照镜子与对称性

想象你站在镜子前：

• 如果你长得完全不对称（比如左眼是红的，右眼是蓝的），那么无论你如何旋转或翻转，镜子里的你看起来都和原来不一样。这时候，你的“对称性”是零（或者说，只有“不动”这一种操作能让你看起来没变）。
• 如果你长得高度对称（比如一个完美的圆球），无论你如何旋转，它看起来都一样。这时候，你的“对称性”很高，有很多操作都能让它“保持不变”。

在数学里：

• 非平凡稳定子 = 高度对称（有很多操作能让函数看起来没变）。
• 平凡稳定子 = 完全不对称（除了什么都不做，没有任何操作能让函数看起来没变）。

论文的结论是：
如果你随机从所有可能的函数里挑一个，它几乎肯定是那种“完全不对称”的（只有平凡稳定子）。那些拥有“高度对称性”（非平凡稳定子）的函数，就像宇宙中的独角兽一样，极其罕见，数量少到可以忽略不计。

4. 这意味着什么？（两个重要推论）

基于这个发现，作者解决了开头提出的两个问题：

推论一：分类数量的“傻瓜公式”是准的

以前，计算有多少个“独特类别”很复杂，因为要扣除那些“对称”的函数。
但现在，既然绝大多数函数都是“不对称”的（没有对称性），那么：

独特类别的数量 ≈ 总函数数量 ÷ 变换规则的数量

这就好比：如果你有一亿个完全不对称的乐高模型，不管你怎么旋转它们，它们都不会重合。所以，你只需要把总数除以旋转方式的总数，就能得到大概有多少种不同的模型。论文证明了，这个“傻瓜公式”在数学上是极其精确的，误差几乎为零。

推论二：随机搜索非常安全

如果你随机生成两个 S 盒，它们属于同一类的概率低得吓人（比中彩票头奖的概率还要低无数个数量级）。

• 比喻：想象你在一个巨大的图书馆里随机抽两本书。因为书太多了，而且每本书的内容都独一无二，你抽到两本“内容本质相同”的书的概率，几乎等于零。
• 实际意义：密码学家在寻找更好的 S 盒时，可以放心大胆地随机生成。不用担心浪费时间在重复的“双胞胎”上。随机生成的结果几乎肯定是全新的、独特的。

5. 总结

这篇论文用数学证明了：
在密码学使用的函数世界里，“平庸”和“重复”是极其罕见的。

• 绝大多数函数都是特立独行的（没有隐藏的对称性）。
• 因此，我们计算独特函数的数量非常简单（直接除法）。
• 随机寻找好函数非常高效，几乎不会遇到“撞车”的情况。

这就好比在说：在这个巨大的宇宙里，每个人都是独一无二的，你不需要担心随机遇到一个和你完全一样的人。这对于设计安全、多样的密码系统来说，是一个非常好的消息。

技术摘要

这是一份关于论文《Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers》（几乎所有向量函数都具有平凡的扩展仿射稳定子）的详细技术总结。

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

向量布尔函数（Vectorial Boolean Functions）在对称密码学中至关重要，通常用作分组密码和哈希函数中的 S 盒。为了评估和设计这些函数，密码学家通常研究它们在特定等价关系下的分类，其中**扩展仿射等价（EA-equivalence, Extended-Affine Equivalence）**是最基本的等价关系之一。EA 等价保持了差分均匀性、Walsh 谱和代数次数等关键密码学性质。

该研究主要解决两个核心问题：

1. 分类问题：究竟有多少个不同的 EA 等价类？由于 EA 等价的函数具有相同的密码学性质，等价类的数量决定了本质上不同的密码原语的数量。
2. 随机采样问题：在通过随机生成搜索具有优良性质的函数时，是否存在重复采样到 EA 等价函数的风险？即随机搜索在模 EA 等价的意义下是否仍然有效？

这两个问题都紧密依赖于**EA 稳定子群（EA-stabilizer）**的结构。一个函数 $F$ 的 EA 稳定子是指所有满足 $A_{out} \circ F \circ A_{in} = F$ 的仿射置换对 $(A_{out}, A_{in})$ 的集合。根据轨道 - 稳定子定理（Orbit-Stabilizer Theorem），等价类的大小与稳定子的大小成反比。如果大多数函数的稳定子是平凡的（即只包含单位元），那么等价类的数量将接近“朴素估计”（总函数数除以群的大小），且随机碰撞的概率将极低。

然而，由于函数空间随输入维度呈双重指数级增长，直接计算稳定子几乎是不可能的。

2. 方法论 (Methodology)

作者采用概率组合学和群作用理论相结合的方法，证明了在有限域上的向量函数空间中，具有非平凡 EA 稳定子的函数是极其罕见的。

主要技术步骤包括：

• 群作用定义：定义扩展仿射群 $\Gamma = \text{AGL}(U) \times \text{AGL}(W)$ 在函数集合 $\mathcal{F}$ 上的共轭作用。
• 不动点分析 (Fixed-point Analysis)：
  • 利用引理分析非平凡仿射置换的不动点结构。证明非平凡仿射置换的不动点集要么为空，要么是一个维度不超过 $n-1$ 的仿射子空间。
  • 推导非平凡仿射置换的轨道数量上界。
• 固定点集大小上界 (Bounding $|Fix(g)|$)：
  • 对于 $\Gamma$ 中的非平凡元素 $g$，分析满足 $g \cdot F = F$ 的函数 $F$ 的数量。
  • 将定义域分解为 $g$ 作用下的轨道，证明在每个轨道上，函数值的自由度受到严格限制。
  • 得出关键不等式：$|Fix(g)| \leq q^{c m q^n}$，其中 $c < 1$ 是一个与 $n, m$ 无关的常数。这意味着满足非平凡对称性的函数数量相对于总函数空间 $q^{mq^n}$ 是指数级小的。
• 并集界 (Union Bound)：
  • 利用并集界（Union Bound）将所有非平凡群元素对应的“非平凡稳定子”事件概率相加。
  • 结合群 $\Gamma$ 的大小（多项式级或指数级，但远小于函数空间的大小），证明随机选取一个函数具有非平凡稳定子的概率随维度呈超指数级衰减（super-exponentially small）。
• Burnside 引理应用：
  • 利用 Burnside 引理计算轨道（等价类）的总数，结合上述稳定子平凡性的结论，推导等价类数量的渐近公式。

3. 主要贡献 (Key Contributions)

1. 主要定理 (Theorem 3.4)：证明了对于均匀随机选取的向量函数 $F: \mathbb{F}_q^n \to \mathbb{F}_q^m$，其具有非平凡 EA 稳定子的概率以 $q^{-\Omega(m q^n)}$ 的速度超指数级衰减。这意味着几乎所有向量函数都具有平凡的 EA 稳定子。
2. 等价类计数公式 (Corollary 3.7)：证明了 EA 等价类的数量渐近等于“朴素估计”（即总函数数 $|\mathcal{F}|$ 除以 EA 群的大小 $|\Gamma|$），且相对误差趋于零。这为计算等价类数量提供了一个简单且概念清晰的渐近公式。
3. 碰撞概率界限 (Proposition 3.8 & Corollary 3.9)：
   • 推导了 EA 等价和 CCZ 等价的碰撞概率上界。
   • 特别地，利用平凡稳定子结果，证明了 EA 等价的碰撞概率上界是渐近紧确的。两个独立随机采样的函数是 EA 等价的概率为 $q^{-\Omega(q^n)}$（在二进制情况下为 $2^{-\Omega(2^n)}$），这是一个超指数级小的概率。

4. 关键结果 (Results)

• 平凡稳定子的普遍性：在函数空间中，具有非平凡 EA 稳定子的函数构成了一个指数级稀有的子集。对于现代密码学中常用的参数（如 8 位 S 盒，$n=m=8$），随机函数具有非平凡稳定子的概率小于 $2^{-368}$，这在数值上几乎为零。
• 等价类数量的精确性：EA 等价类的总数 $|\mathcal{F}/\Gamma|$ 满足：
  $$\frac{|\mathcal{F}/\Gamma|}{|\mathcal{F}|/|\Gamma|} = 1 + o(1)$$
  这表明群作用在渐近意义下是自由的（asymptotically free）。
• 随机采样的有效性：由于碰撞概率极低，随机生成向量布尔函数以寻找具有特定密码学性质（如 APN 或 AB 函数）的策略是高度有效的。研究人员可以随机采样而无需担心因 EA 等价导致的冗余。

5. 意义与影响 (Significance)

• 理论验证：该研究从理论上验证了密码学设计中广泛使用的随机采样策略的有效性。它表明，在寻找优良 S 盒时，随机搜索不会在 EA 等价类中“打转”，因为碰撞概率微乎其微。
• 结构化搜索的指导：结果指出，具有非平凡稳定子的函数（通常具有某种对称结构）在空间中极其罕见。这暗示了在设计 S 盒时，如果刻意寻找具有对称性的结构，可能会极大地缩小搜索空间，但也意味着大多数随机生成的函数天然具有“无结构”（即平凡稳定子）的特性。
• 统一现有研究：该工作统一了关于布尔函数稳定子（如 Clausen, Clote-Kranakis 的工作）和等价类计数（如 Hou, Lu 等人的工作）的两条研究路线。它通过概率方法重新推导了之前的渐近计数结果，并揭示了其背后的结构性原因：稳定子的平凡性。
• 开放问题：虽然论文解决了 EA 等价的问题，但关于CCZ 等价（Carlet-Charpin-Zinoviev 等价，比 EA 更一般）是否也具有类似的“大多数函数具有平凡稳定子”的性质，目前仍是一个开放问题。由于 CCZ 等价基于函数图的仿射等价，其群作用更为复杂，需要新的技术来解决。

总结：这篇论文通过严谨的概率分析，确立了向量函数空间中“平凡稳定子”的普遍性，解决了 EA 等价类的计数和随机采样效率问题，为对称密码原语的设计提供了坚实的理论基础。