🔢 mathematics

The combinatorial structure and value distributions of plateaued functions

本文研究了从 $\mathbb{F}_p^n$ 到 $\mathbb{F}_p^m$ 的 plateaued 函数的组合结构，重点探讨了其 Walsh 变换、线性度、差分性质与值分布（特别是像集和原像集大小）之间的相互作用，并针对“几乎平衡”的 plateaued 函数（包括单变量幂函数）建立了存在性条件、线性度公式及差分均匀性界限。

原作者： Lukas Kölsch, Alexandr Polujan

发布于 2026-03-26

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Lukas Kölsch, Alexandr Polujan

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

这篇论文就像是在密码学世界的“乐高积木”工厂里，进行的一次深度质检和结构分析。

为了让你轻松理解，我们把这篇论文里的专业术语翻译成生活中的比喻：

1. 核心角色：什么是“平台函数”（Plateaued Functions）？

想象一下，密码学中的函数就像是一个巨大的迷宫，或者是一个复杂的筛子。

输入：你扔进去一堆数字（比如你的密码）。
输出：筛子吐出来另一堆数字。

在这个世界里，有一类特殊的函数叫**“平台函数”。你可以把它们想象成地形平坦的高原**：

有些函数像悬崖（太简单，容易被破解）。
有些函数像完美的山峰（太完美，很难构造，比如“弯曲函数”Bent functions）。
平台函数就像高原：虽然中间有起伏，但大部分地方是平坦的。

为什么它们很重要？
因为现代加密算法（比如保护你手机安全的算法）需要这些“高原”作为基石。它们既不像悬崖那样脆弱，也不像完美的山峰那样难以制造。著名的“二次函数”和很多“抗差分攻击（APN）”的函数，本质上都是这种“高原”。

2. 研究目的：我们要查什么？

作者 Lukas 和 Alexandr 想搞清楚两件事：

分布情况（Value Distribution）：当你扔进很多不同的数字时，这个“筛子”吐出来的结果是怎么分布的？
- 比喻：如果这是一个公平的彩票机，每个号码被抽中的次数应该差不多（这叫“平衡”）。如果某个号码被抽中了几万次，而另一个只抽中了一次，那这个机器就有问题（这叫“不平衡”）。
- 这篇论文研究的是那些**“几乎平衡”**的机器：除了一个号码特别倒霉（或特别幸运）外，其他号码的分布都很均匀。
结构联系：这种分布情况，和函数的“内部构造”（比如它的线性程度、抗攻击能力）有什么关系？

3. 主要发现：他们发现了什么“秘密”？

作者发明了一套新的**“透视眼镜”**（基于数学中的 Walsh 变换），透过它看这些函数，发现了很多惊人的规律：

A. “几乎平衡”的函数有严格的规矩

以前人们知道有些函数是“几乎平衡”的，但不知道它们为什么能这样。

发现：作者证明，如果一个函数是“几乎平衡”的，那么它的内部结构必须非常特殊。就像只有特定形状的积木才能拼成完美的拱门。
比喻：如果你发现一个筛子，除了一个洞漏得特别多，其他洞漏得都一样多，那么这个筛子的孔洞大小（振幅）必须满足特定的数学公式，不能是随便乱造的。

B. 单变量幂函数（Monomials）的“独裁”

很多加密算法喜欢用简单的公式，比如 $F(x) = x^d$ （就像只有一种规则的筛子）。

发现：作者发现，这种简单的“单规则”函数，如果要是“平台函数”，它的规则（指数 $d$ ）必须非常非常挑剔。
比喻：这就好比你想用只有一种形状的积木（比如全是三角形）去搭一个复杂的城堡。作者发现，只有当三角形的角度是特定的（比如 $2^t + 1$ 这种形式）时，你才能搭出既稳固（抗攻击）又平坦（平台）的城堡。其他的形状根本搭不起来。

C. 关于“最坏情况”的警告

在密码学中，我们最怕函数“太不均匀”。

发现：作者计算了这些函数的“不平衡度”（Imbalance）。他们发现，对于某些特定的高级函数（APN 函数），如果它们的不平衡度达到了某个极限，那么它们的内部结构就不可能是某种特定的样子。
比喻：就像侦探破案，如果嫌疑人的指纹（不平衡度）显示他在 A 地，那么他就不可能同时在 B 地。作者利用这个逻辑，排除了某些函数存在的可能性。

4. 具体贡献：他们造了什么新工具？

新的尺子：他们建立了一个公式，只要知道函数的“不平衡度”，就能算出它的输出结果最多能偏离平均值多少。这就像给筛子定了一个**“最大误差标准”**。
分类学：他们把那些“几乎平衡”的函数分门别类，发现它们其实只有几种特定的“长相”。
新建筑方案：他们不仅分析了现有的，还提出了一些新的方法（比如 Maiorana-McFarland 构造法），可以像搭乐高一样，用特定的零件拼出符合要求的“几乎平衡”函数。

5. 总结：这对我们意味着什么？

这就好比在设计防弹衣。

以前的科学家知道防弹衣（加密函数）要结实。
这篇论文告诉我们：什么样的材料（数学结构）既能保证防弹（抗攻击），又能保证轻便（计算快），而且还能做到“几乎均匀”（没有明显的弱点）。

一句话总结：
这篇文章通过数学显微镜，揭示了密码学中一类重要函数（平台函数）的内部骨架。它告诉我们，想要制造出既安全又高效的加密工具，不能随便乱搭，必须遵循严格的**“积木拼搭规则”。这不仅帮助科学家理解现有的加密算法，也为未来设计更安全的密码系统提供了设计蓝图**。

这是一份关于论文《Plateaued 函数的组合结构与值分布》（The combinatorial structure and value distributions of plateaued functions）的详细技术总结。

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

背景：
Plateaued 函数（平台函数）是二次函数、 Bent 函数（弯曲函数）以及大多数已知 APN（Almost Perfect Nonlinear，几乎完美非线性）函数的推广。它们在密码学中至关重要，常作为构建块用于设计 S 盒、哈希函数（如 Keccak, Ascon）和零知识证明系统（如 Poseidon, Rescue-Prime）。

核心问题：
尽管 plateaued 函数在密码学应用中广泛存在，但对其值分布（Value Distribution）（即像集大小和原像集大小的分布）的深入理解仍然不足。特别是：

如何量化函数偏离“平衡”（Balanced，即所有像的原像大小相等）的程度？
Plateaued 函数的 Walsh 变换特性与其值分布、线性度（Linearity）及差分均匀性（Differential Uniformity）之间存在怎样的内在联系？
是否存在特定类型的 Plateaued 函数（如 $d$ -to-1 函数或单项式函数），其值分布具有特殊的组合结构（如“几乎平衡”）？
对于具有最小像集大小的 Plateaued APN 函数，其可能的值分布有哪些限制？

2. 方法论 (Methodology)

本文主要利用**Walsh 变换（Walsh Transform）**作为核心工具，结合组合数学和数论方法进行分析。

Walsh 变换与原像集的联系： 作者利用 Walsh 变换在 $a=0$ 处的性质，建立了原像集大小 $|F^{-1}(\beta)|$ 与 Walsh 系数 $W_F(b, 0)$ 之间的精确数学关系。特别是利用二阶矩 $\sum |W_F(b, 0)|^2$ 来推导原像集大小的平方和。
不平衡度（Imbalance）的定义： 引入并推广了不平衡度 $N_bF$ 的概念，定义为 $\frac{1}{p^m} \sum_{b \neq 0} |W_F(b, 0)|^2$ 。这是衡量函数偏离平衡程度的关键指标。
不等式推导： 利用柯西 - 施瓦茨不等式（Cauchy-Schwarz inequality），推导了原像集大小的上下界，并定义了达到这些界限的“几乎平衡”（Almost Balanced）函数。
代数结构分析： 针对 Plateaued 函数（其 Walsh 谱值仅取有限个特定值），结合分圆域（Cyclotomic fields）的性质，分析 $d$ -to-1 映射和单项式函数的存在性条件。
差分均匀性分析： 通过 Walsh 变换的四阶矩（Fourth moment）与差分映射的解数之间的关系，推导差分均匀性的下界。

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

3.1 理论框架：原像集大小与不平衡度的界限

定理 3.3： 给出了任意映射 $F: \mathbb{F}_p^n \to \mathbb{F}_p^m$ 的原像集大小的上下界，界限由像集大小 $|Im(F)| $和不平衡度$ N_bF$ 决定。
定义 3.7（几乎平衡函数）： 定义了“几乎平衡”函数，即除了一个像的原像大小不同外，其余所有非空原像大小均相等。这类函数在值分布意义上最接近平衡函数。
定理 4.1： 建立了满射几乎平衡 Plateaued 函数的 Walsh 变换特性。指出对于此类函数，所有非零 $b$ 对应的 $W_F(b, 0)$ 的模长必须相等，且 $N_bF$ 与该模长直接相关。

3.2 Plateaued $d$ -to-1 函数的分类

定理 5.2： 这是一个核心结果。证明了如果 Plateaued 函数是 $d$ $d$ -to-1 的（即有一个原像大小为 1，其余非空原像大小为 $d$ $d$ ），则 $d$ $d$ 必须具有非常特定的形式： $d = p^t + 1$ $d = p^{t} + 1$ （其中 $t \ge 1$ $t \geq 1$ 且 $t | n/2$ $t ∣ n /2$ ）。
- 此类函数的分量函数由两类组成：一部分是 Bent 函数，另一部分是振幅为 $p^{n/2+t}$ 的 Plateaued 函数。
- 推论 5.4 指出，由单项式 $x^d$ 诱导的 Plateaued 映射要么是置换（ $d=1$ ），要么是 $(p^t+1)$ -to-1 映射。
定理 5.5 & 5.6： 建立了 Plateaued 函数的差分均匀性 $\delta$ $δ$ 与其振幅参数的关系。
- 对于 $(p^t+1)$ -to-1 的 Plateaued 函数，其差分均匀性至少为 $p^t$ 。
- 当且仅当函数是“差分双值”（Differentially 2-valued，即差分方程解数为 0 或 $p^t$ ）时，差分均匀性恰好为 $p^t$ 。

3.3 具体构造与几乎平衡性

定理 5.8： 分析了一类基于迹函数（Trace function）的单项式构造 $F(x) = Tr(x^{2^r+1})$ ，证明了在特定条件下，这些函数是满射且几乎平衡的，并给出了具体的原像集大小公式。
命题 5.9 & 5.10： 研究了 Maiorana-McFarland 构造的 Plateaued 函数，展示了如何通过选择适当的组件函数（如 2-to-1 映射 $\pi$ ）来构造出平衡或几乎平衡的 Plateaued 函数。

3.4 Plateaued APN 函数的组合结构

命题 6.3： 给出了 Plateaued APN 函数不平衡度 $N_bF$ $N_{b} F$ 的上下界： $(2^{n+1}-2)/3 \le N_bF \le 2^{n+1}-2$ $(2^{n + 1} - 2) /3 \leq N_{b} F \leq 2^{n + 1} - 2$ 。
- 下界对应于具有最大数量 Bent 分量函数的情况。
- 上界对应于没有平衡分量函数的情况。
引理 6.4 & 命题 6.5： 证明了对于偶数 $n$ ，Plateaued APN 函数的不平衡度满足 $N_bF \equiv 2 \pmod 4$ ，且 Bent 分量的数量也满足特定的模 4 同余性质。
定理 6.7（重要排除结果）： 针对具有最小像集大小（ $|Im(F)| = (2^{n+2})/3$ ）的 APN 函数，已知其有三种可能的值分布。本文证明：Plateaued APN 函数不可能具有第二种值分布（即两个原像大小为 2，其余为 3）。这通过计算 $N_bF$ 并发现其与引理 6.4 的模 4 性质矛盾而得证。
定理 6.8： 证明了具有最小像集大小的 Plateaued APN 函数不能包含任何平衡的分量函数。

4. 意义与影响 (Significance)

统一了分析框架： 本文成功地将 Walsh 变换的谱特性与函数的组合结构（值分布）联系起来，提供了一种不依赖具体差分性质即可分析函数值分布的新方法。
限制了构造空间： 通过证明 Plateaued $d$ -to-1 函数仅存在于 $d=p^t+1$ 的情况，极大地缩小了寻找此类特殊函数的搜索空间，为密码算法设计中的 S 盒选择提供了理论指导。
解决了存在性问题： 通过排除具有最小像集大小的 Plateaued APN 函数的某种特定值分布（Theorem 6.7），解决了该领域的一个开放性问题，并暗示了第三类分布可能是唯一可能的候选者（这也是作者提出的未来研究方向）。
密码学应用指导： 研究结果揭示了 Plateaued 函数在平衡性、非线性度和差分均匀性之间的权衡（Trade-off）。例如，具有特定差分均匀性的 Plateaued 函数必然具有特定的分量函数结构，这有助于评估现有密码原语的安全性或指导新原语的设计。
推广了现有理论： 将关于 Bent 函数和 APN 函数的已知结果推广到了更广泛的 Plateaued 函数类，并引入了“几乎平衡”这一概念在非满射情况下的推广。

总结

该论文通过深入分析 Walsh 变换的谱特性，揭示了 Plateaued 函数（特别是 APN 函数）在值分布、线性度和差分均匀性方面的深刻组合结构。主要成果包括确定了 Plateaued $d$ -to-1 函数的存在性条件、建立了不平衡度与分量函数类型的精确关系，并排除了某些特定值分布在 Plateaued APN 函数中的可能性。这些结果为理解密码学原语的组合性质提供了强有力的理论工具。