🔢 mathematics

On Generalizations of Maiorana-McFarland and $\mathcal{PS}_{ap}$ Functions

本文通过利用二阶导数与代数曲线理论，构造了不属于完成 Maiorana-McFarland 或 $\mathcal{PS}_{ap}$ 类的广义 Bent 函数族，证明了特定条件下广义 $\mathcal{PS}_{ap}$ 函数无法分解为 Bent 或半 Bent 函数，并提出了一种基于向量广义 $\mathcal{PS}_{ap}$ 函数分量拼接的二次构造方法。

原作者： Sezel Alkan, Nurdagül Anbar, Athina Avrantini, Erroxe Etxabarri-Alberdi, Tekgül Kalaycı, Beatrice Toesca

发布于 2026-03-31

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Sezel Alkan, Nurdagül Anbar, Athina Avrantini, Erroxe Etxabarri-Alberdi, Tekgül Kalaycı, Beatrice Toesca

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

这篇论文就像是在密码学的“乐高世界”里，寻找那些既坚固又独特的新积木。

为了让你轻松理解，我们可以把这篇论文的核心内容想象成是在建造一座**“绝对安全的数字堡垒”**。

1. 背景：什么是“弯曲函数”（Bent Functions）？

想象一下，你在设计一个超级复杂的密码锁。这个锁的机制必须非常“混乱”，以至于任何试图猜测密码的人（黑客）都找不到规律。在数学里，这种极度混乱、没有任何线性规律可循的函数，就叫**“弯曲函数”**（Bent Functions）。

为什么重要？ 它们是现代加密技术（比如保护你的银行卡、手机通讯）的基石。如果函数太有规律，密码锁就被轻易撬开了。
现状： 数学家们已经知道两种制造这种“完美混乱”的经典方法（就像两种经典的乐高搭建法）：
1. Maiorana-McFarland (MM) 类：一种很老派但很常用的搭建法。
2. PSap 类：另一种基于“散开”结构的搭建法。

问题在于： 过去几十年里，大家发现，用这两种老方法造出来的锁，虽然好，但数量太少，而且容易被某种特定的数学工具（叫“二阶导数”）识破。我们需要全新的、老方法造不出来的“超级混乱”积木。

2. 论文的第一大贡献：造出了“新 MM 积木”

核心故事： 作者们想：“既然老方法（MM 类）造不出所有可能的完美混乱，那我们就把老方法‘升级’一下，造出一种看起来像 MM，但实际上不是 MM的新积木。”

比喻： 想象 MM 类积木就像是用完全相同的砖块砌墙。虽然墙很结实，但如果你发现墙里有一块砖的纹理和别的完全一样，你就知道它是老方法造的。
作者的做法： 他们发明了一种**“混合拼接法”**。
- 他们把不同的“砖块”（数学函数）拼在一起。
- 关键点在于：这些砖块虽然看起来很像，但它们内部的“纹理”（数学上的 M-子空间）是互不兼容的。
- 结果： 他们成功造出了一批新函数。如果你试图用老方法（MM 类）去分析它们，会发现它们“对不上号”。这就证明了这些新函数完全独立于旧体系，是真正的“新物种”。

简单总结： 他们证明了，只要把几种特定的旧积木以特殊方式“错位”拼接，就能造出一种全新的、旧方法无法模仿的超级混乱函数。

3. 论文的第二大贡献：拆解“散开积木”的奥秘

核心故事： 接下来，作者们研究了另一种经典积木——PSap 类（基于“散开”结构的积木）。

旧观念： 以前大家觉得，这种积木可能只是由更小的、简单的“半混乱”积木（半弯曲函数）拼起来的。就像有人觉得复杂的乐高城堡其实只是几个小房子的简单堆叠。
作者的发现： 作者们通过复杂的数学计算（利用代数曲线理论，这就像是用显微镜看积木内部的分子结构），证明了：当积木足够“小”（数学上的度数足够低）时，这种 PSap 积木是“浑然一体”的！
比喻： 想象一块天然的玉石。以前人们以为它是由几块小石头粘在一起的（拼接而成）。但作者证明，在特定条件下，这块玉石是天然生长的，你无法把它拆解成更小的、独立的“半玉石”而不破坏它。
意义： 这意味着，这种函数不能通过简单的“拼接”旧函数来得到。它们是真正的“原生”复杂结构，这进一步证明了它们的独特性和安全性。

4. 论文的第三大贡献：用“向量”造新锁

核心故事： 最后，作者们玩了一个更高级的游戏。

比喻： 之前的积木都是单色的（输出 0 或 1）。现在，他们造了一种**“多色积木”**（向量函数），一块积木能同时输出多种颜色（多个值）。
操作： 他们把这种“多色积木”拆分成几个单色的小块，然后像拼马赛克一样，把这些小块重新拼成一个新的、更大的单色积木。
结果： 这种新的拼接方式，竟然又产生了一种全新的、安全的弯曲函数。这就像是用不同颜色的乐高砖块，拼出了一幅全新的、以前没人见过的图案。

5. 总结：这篇论文到底说了什么？

如果把密码学比作**“建造防御黑客的迷宫”**：

过去： 我们只有两种造迷宫的图纸（MM 和 PSap），而且大家发现这两种图纸造出来的迷宫，有些角落容易被黑客找到规律。
这篇论文做了什么？
- 创新 1： 他们把旧图纸改了一下，造出了旧图纸造不出来的新迷宫（广义 MM 函数），让黑客更找不到北。
- 创新 2： 他们发现，有些新迷宫是天然形成的，根本不能通过简单的“拼接”旧迷宫得到（广义 PSap 函数的不可分解性），这打破了人们的固有认知。
- 创新 3： 他们发明了一种**“马赛克拼接术”**，把复杂的彩色迷宫拆散重组，造出了更多新的安全迷宫。

一句话总结：
这篇论文通过巧妙的数学技巧，打破了旧有分类的界限，证明了存在大量“独一无二”的加密函数，并展示了如何从复杂的结构中创造出新的安全基石，为未来的密码安全提供了更丰富的“武器库”。

作者们就像是一群数学界的乐高大师，他们不仅发现了新的积木块，还证明了这些积木块有着前所未有的、无法被简单复制的复杂结构。

这是一份关于论文《Maiorana–McFarland 和 PSap 函数的一般化》（On Generalizations of Maiorana–McFarland and PSap Functions）的详细技术总结。

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

布尔弯曲函数（Boolean bent functions）在密码学和编码理论中具有重要地位，因为它们具有最大的非线性度。构造弯曲函数主要有两类方法：

初级构造（Primary Constructions）： 直接从代数结构生成，如 Maiorana–McFarland (MM) 类和部分展开（Partial Spread, PS）类。
次级构造（Secondary Constructions）： 基于已知弯曲函数通过拼接（concatenation）或其他变换生成。

核心问题：

MM 类的覆盖范围： 已知在低维（ $n \le 6$ ）下，所有弯曲函数都属于 MM 类的完成类（ $MM^\#$ ）。但在更高维下，存在不属于 $MM^\#$ 的弯曲函数。如何系统地构造并证明这些函数确实位于 $MM^\#$ 之外是一个活跃的研究领域。
PSap 类的分解性： 广义 PSap（Desarguesian partial spread）函数是一类重要的弯曲函数。研究它们是否可以通过次级构造（特别是通过拼接弯曲或半弯曲函数）获得至关重要。如果它们不能分解，则意味着它们具有独特的结构，无法通过简单的拼接方法生成。
一般化与分类： 现有的广义 MM (GMM) 和广义 PSap 函数构造中，许多函数的等价类归属尚不明确，需要更精细的判别准则。

2. 方法论 (Methodology)

本文主要采用了以下数学工具和理论框架：

二阶导数与 Dillon 判据： 利用 Dillon 提出的判据，即一个布尔弯曲函数属于 $MM^\#$ 类当且仅当存在一个维度为 $n/2$ 的 $M$ -子空间（M-subspace），使得该子空间上的二阶导数恒为零。
代数曲线与函数域理论： 利用有限域上的代数曲线（特别是 Artin-Schreier 曲线）的有理点数量估计（Hasse-Weil 界），来证明某些二阶导数不是常数函数，从而排除分解的可能性。
Walsh 变换与对偶函数： 分析函数的 Walsh 谱及其对偶函数的性质，特别是利用对偶函数的二阶导数来判断原函数是否允许弯曲或半弯曲分解。
向量函数与分量分析： 研究向量值弯曲函数的分量函数性质，特别是利用分量函数对偶之间的线性关系来构造新的弯曲函数。

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

3.1 构造位于 $MM^\#$ 类之外的广义 MM (GMM) 函数

构造方法： 作者提出了一种新的 GMM 构造方法。该方法基于两个具有特定性质的 MM 函数：
1. 一个 MM 函数 $h$ ，其拥有唯一的 $n/2$ 维 $M$ -子空间 $W$ ，且所有非平凡 $M$ -子空间都包含在 $W$ 中。
2. 通过线性置换 $L$ 将 $h$ 映射到其补空间，构造出一组函数 $f^{(z)}$ 。
关键定理 (Theorem 1, Corollaries 7 & 9)：
- 证明了当参数满足特定条件（如 $m > k + 2$ ）时，构造出的 GMM 函数 $f(x, y, z)$ 不属于 $MM^\#$ 类。
- 具体地，证明了这些函数的任何 $M$ -子空间的维度严格小于 $n/2 + k$ ，从而不满足 $MM^\#$ 类的充要条件（即存在维度为 $n/2+k$ 的 $M$ -子空间）。
- 给出了具体的置换多项式实例，如逆函数 $\pi(x) = x^{2^m-2}$ 和 Gold 函数 $\pi(x) = x^{2^k+1}$ （在特定条件下），确保构造出的函数满足上述性质。
意义： 这提供了显式的、非等价的弯曲函数族，它们既不在 MM 类也不在 PSap 类中，丰富了弯曲函数的分类。

3.2 广义 PSap 函数的分解性研究

研究目标： 探究广义 PSap 函数是否可以通过拼接（concatenation）弯曲或半弯曲函数得到。这等价于研究其对偶函数是否允许半弯曲分解（即是否存在非平凡的 $M$ -子空间）。
主要结果 (Proposition 12, Theorem 2)：
- 证明了当广义 PSap 函数的定义域有限域大小相对于其代数次数足够大时（具体条件涉及 $m$ 和 $e$ 的关系，如 $m \ge 4$ 且次数较低），这些函数通常不能被分解为弯曲或半弯曲函数。
- 利用代数曲线有理点数量的下界估计（Lemma 14），证明了其二阶导数不是常数（既不全为 0 也不全为 1）。
- Corollary 15 & Example 4.1： 针对具体的 Gold 函数构造的广义 PSap 函数，证明了在特定参数下，它们既没有弯曲分解也没有半弯曲分解。
推论： 这意味着这类广义 PSap 函数不能通过已知的基于拼接的次级构造方法获得，它们代表了弯曲函数空间中更“原始”或更复杂的结构。

3.3 基于向量广义 PSap 函数分量的次级构造

新构造 (Theorem 3 & 4)：
- 受向量值广义 PSap 函数分量性质的启发（即分量对偶函数满足特定的线性关系 $(F_\alpha)^* + (F_\beta)^* = (F_{\alpha+\beta})^*$ ），作者提出了一种新的次级构造方法。
- 通过拼接向量广义 PSap 函数的特定分量，构造出了新的布尔弯曲函数。
- 该构造利用了广义 Desarguesian 展开（Generalized Desarguesian spread）的预像分布特性，给出了一个通用的弯曲函数构造框架。

4. 技术细节与证明逻辑

关于 $MM^\#$ 的排除： 核心在于计算二阶导数 $D_a D_b f$ 。如果 $f$ 属于 $MM^\#$ ，则存在一个大维度的子空间使二阶导数为 0。作者通过构造特殊的 $f^{(z)}$ 组合，使得任何试图寻找大维度 $M$ -子空间的尝试都会导致矛盾（即导数不恒为 0），从而证明其不在 $MM^\#$ 中。
关于不可分解性： 核心在于证明对偶函数 $f^*$ 的二阶导数 $D_u D_v f^*$ 不是常数。作者将这一问题转化为代数曲线 $Z^2 + Z = P(\dots)$ 是否有有理点的问题。通过 Hasse-Weil 界证明，在给定参数下，曲线既有取值为 0 的点也有取值为 1 的点，因此二阶导数非常数，从而排除了分解的可能性。

5. 研究意义 (Significance)

扩展了弯曲函数的构造理论： 提供了新的、显式的构造方法，生成了位于经典 $MM^\#$ 类之外的弯曲函数，填补了现有构造理论的空白。
深化了对 PSap 类结构的理解： 揭示了广义 PSap 函数在特定条件下具有“不可分解”的内在性质，表明它们不能简单地通过拼接已知函数生成，这为理解弯曲函数的复杂结构提供了新视角。
方法论的创新： 成功地将代数几何（代数曲线、函数域）工具应用于布尔函数的分类和性质证明中，展示了跨学科方法在组合数学和密码学中的强大威力。
对密码学的启示： 由于弯曲函数是构造 S 盒和流密码的关键组件，发现新的、结构独特的弯曲函数有助于设计具有更好抗攻击能力（如更高的非线性度、更好的扩散性）的密码原语。

综上所述，该论文通过严谨的代数分析和几何工具，不仅构造了新的弯曲函数族，还深刻揭示了现有主要构造类（MM 和 PSap）的边界和内部结构，是布尔函数理论领域的重要进展。