🔢 mathematics

Bent Functions and the Completed Maiorana-McFarland Class

本文综述了布尔弯函数设计与分析方面的基础结果及最新进展，特别侧重于它们与完全 Maiorana-McFarland 类之间的关系。

原作者： Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

发布于 2026-08-25

📖 1 分钟阅读🧠 深度阅读

原作者： Enes Pasalic, Alexandr Polujan, Fengrong Zhang, Sadmir Kudin

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

在现代数字安全的隐藏架构中，存在着一种被称为“弯函数”（bent function）的特殊数学对象。它们并非物理设备或生物实体，而是处理二进制数据的复杂规则——这些由0和1组成的字符串构成了所有计算机通信的基础。想象一个由各种可能规则组成的广阔景观，其中大多数规则是可预测且易于分析的。弯函数则处于这种不可预测性的巅峰，它们尽可能地远离任何简单的线性模式。由于这种极度的不规则性，它们在密码学和纠错码中作为极其宝贵的工具，扮演着维持数据保护的角色，如同制造出让窃听者无法发现信号的混沌噪声。几十年来，数学家们已知如何构建一类特定的、被充分理解的函数族，这一族被称为由最初描述它们的学者命名的函数。这个被称为 Maiorana-McFarland 类的家族，一直以来都是构建弯函数的主要蓝图，就像建造房屋的标准建筑设计图一样。然而，一个悬而未决的问题一直困扰着该领域：这些标准蓝图是构建此类函数的唯一途径吗？还是说，还存在着我们尚未发现的其他更奇特的方案？

一组研究人员现在对这个问题进行了全面的审视，调查了整个弯函数景观及其与该标准家族的关系。他们的工作证实，已知的蓝图虽然有用，但仅代表了总可能性的极小部分。在变量数为8的具体情况下，计算机搜索显示，弯函数的总数在数量级上是天文数字，大约为 2 的 106 次方。相比之下，使用标准的 Maiorana-McFarland 蓝图构建的函数数量估计最多只有 2 的 81 次方。这一巨大的差距表明，绝大多数弯函数在本质上都不同于那些我们能够显式构造的函数。研究人员的目标是绘制出这两个极端之间的领地，识别出能够确保不符合旧模具的新型构建方法，并理解导致它们如此不同的结构性原因。

论文首先检查了两个被称为 C 类和 D 类的特定弯函数族，这些类别旨在修改标准蓝图。这些家族通过向标准公式引入特定的模式，加入了一些刻意的微调。研究人员调查了这些修改是否足以将生成的函数推离标准家族。他们发现，在特定条件下，这些经过修改的函数确实是截然不同的。例如，如果用于构造的底层置换具有特定的代数属性——本质上，即它缺乏某些隐藏的对称性——那么生成的弯函数就无法被转换回标准形式。作者提供了清晰且可测试的规则，用以判定一个函数属于这些新的、异质的家族，还是仍然受困于旧有的家族。他们还探索了结合了不同修改类型的“超类”（superclasses），发现虽然某些组合有效，但另一些组合却无法产生弯函数，这揭示了维持必要不可预测性水平所需的微妙平衡。

除了这些特定的家族外，研究人员还研究了利用有限域的多项式结构（通常使用迹项/trace terms 来描述）构建的函数。这些函数中的输出取决于一个数经过特定幂次运算后的和。这项研究强调，许多此类函数（特别是基于某些指数的函数）在证明上都属于标准家族之外。研究人员使用了一种涉及二阶导数的特定数学测试——这是一种衡量函数变化率本身如何变化的方法——来证明这些函数缺乏标准类中所具备的结构规整性。他们还研究了作为其他重要数学对象（如几乎完美非线性函数/almost perfect nonlinear functions）指示器的函数，表明这些指示器通常拥有属于弯函数且位于已知家族之外的独特非标准属性。

研究的一个核心主题是“线性指数”（linearity index）的概念，它可以被视为衡量一个函数在多大程度上类似于简单的线性模式。标准的 Maiorana-McFarland 函数具有较高的线性指数，这意味着它们可以被分解为大型的简单仿射块。研究人员识别出了一类具有最小可能线性指数的新类别，他们称之为“最优”（optimal）函数。这些函数是标准函数的对立面；它们是如此不规则，以至于完全无法被简化为大型的仿射块。论文详细介绍了如何构造这些最优函数，并证明它们在本质上与标准类不同。通过研究“M-子空间”（M-subspaces）——即函数定义域内揭示其底层对称性的特殊几何子结构——作者展示了这些最优函数具有一种独特的、极小化的结构，而标准函数并不具备这种结构。

该综述还深入探讨了一个更广泛、更灵活的框架，称为“广义 Maiorana-McFarland 类”。该框架允许构建由不同大小的仿射块（而非标准类中使用的固定大小）组成的函数。研究人员精确地刻画了该类函数在何时仍属于标准家族，以及何时跨出了标准家族。他们发现，通过仔细选择构建模块，可以创造出“近似”标准但仍具差异性的函数，也可以创造出完全异于标准家族的函数。论文最后列出了若干开放性问题，承认尽管他们已经绘制出了这些异质函数中相当一部分的版图，但对所有弯函数的精确计数仍然是一个谜团。他们向未来的研究人员发起挑战，鼓励寻找更多这类异质函数的无穷系列，并理解使它们变得独特的精确代数结构，从而确保该领域能够超越原始蓝图的限制，持续演进。

技术摘要：Bent 函数与完成的 Maiorana-McFarland 类

问题陈述
由 Rothaus 引入的布尔 Bent 函数是偶数个变量中实现最大非线性（与仿射函数距离最大）的一类基本函数。虽然 Maiorana-McFarland (M) 类及其完成版本 ( $M^\#$ ) 是研究最透彻、最显式的 Bent 函数族，但近期的计算证据表明，总体的 Bent 函数数量与属于 $M^\#$ 的函数数量之间存在显著差异。具体而言，在 8 维情况下，Bent 函数的总数约为 $2^{106}$ ，而等价于 Maiorana-McFarland 的函数数量估计最多为 $2^{81}$ 。这一观察结果构成了本综述的核心问题：刻画位于完成的 Maiorana-McFarland 类 ( $M^\#$ ) 之外的 Bent 函数，理解其代数结构，并开发此类函数的显式构造方法。本文的研究重点是“排除问题”——即确定各种 Bent 函数类与 $M^\#$ 的交集，并识别使函数被证明处于该类之外的条件。

方法论
本文采用综合性的综述方法，综合了关于布尔 Bent 函数设计与分析的基础结果及最新进展。其技术方法高度依赖于：

代数刻画： 利用二阶导数判据（引理 1.2）来刻画对 $M^\#$ 的成员资格。一个函数属于 $M^\#$ 当且仅当存在一个 $m$ 维子空间 $U$ ，使得对于所有 $a, b \in U$ ，二阶导数 $D_a D_b f$ 均为零。
线性指数与 M-子空间： 分析“线性指数” ($ind(f) $)，定义为 M-子空间（二阶导数为零的子空间）的最大维度。具有$ ind(f) = n/2 $的函数属于$ M^# $，而具有最小指数 ($ ind(f)=1 $) 的函数被称为$ \ell$-最优函数。
次级构造： 研究诸如直接和、间接和、拼接（2-拼接和 4-拼接）以及添加迹项（trace terms）或子空间指示函数如何影响对 $M^\#$ 的成员资格。
广义框架： 将分析从经典的 $M$ 类 ( $r=s=n/2$ ) 扩展到广义 Maiorana-McFarland (GMM) 类 ( $Mr,s$ )，其中 $f(x,y) = x \cdot \phi(y) + h(y)$ 且 $x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s, r \neq s$ 。

主要贡献与结果

Carlet 的 C 类与 D 类： 本文详细介绍了通过添加向量子空间指示函数来修改 Maiorana-McFarland 形式的 C 类和 D 类。
- C 类： 形如 $x \cdot \pi(y) + 1_{L^\perp}(x)$ 的函数。作者总结了保证该函数为 Bent 且不在 $M^\#$ 中的置换 $\pi$ 和子空间 $L$ 的充分条件（特别是性质 (C)）。一个关键结果涉及其分量缺乏非零线性结构的置换。
- D 类与 $D_0$ 类： 形如 $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ 的函数及其子类 $D_0$ ( $x \cdot \pi(y) + \delta_0(x)$ )。本文提供了对 $D_0 \cap M^\#$ 的完整刻画，表明对于二次置换，其成员资格取决于该置换是否在某个仿射超平面上是仿射的。对于更高阶的函数，通常位于 $M^\#$ 之外。
- 超类（Superclasses）： 综述考察了通过组合指示函数形成的超类（SC, CD, SD）。研究发现，虽然某些组合（如 SC）能产生 $M^\#$ 之外的 Bent 函数，但其他组合（如 SD）则完全无法产生 Bent 函数。
迹项与 $P_\tau$ 性质：
- 本文回顾了通过迹项（例如 Dillon 和 Kasami 指数）定义的单项式、双项式及相关 Bent 函数。它证实了许多此类函数（特别是具有特定 Niho 指数的函数）位于 $M^\#$ 之外。
- 文中用了大量篇幅讨论 $P_\tau$ 性质，这涉及向 Bent 函数添加迹项的多项式组合。论文详细说明了以对偶函数的二阶导数消失为特征的 $P_\tau$ 性质，如何允许构造出不在 C 或 D 类中的、属于 $M^\#$ 之外的无限 Bent 函数族。
广义 Maiorana-McFarland (GMM) 类：
- 本文引入了 GMM 类 ( $Mr,s$ ) 及其完成版本。它利用“Bent 集”和“部分定义 Bent 函数”来刻画该类中的 Bent 性。
- 几乎 Maiorana-McFarland ( $k=1$ )： 对线性指数为 $n/2 - 1$ 的函数进行了分析。论文区分了定义域的“平凡”、“非适当”和“适当”划分，表明特定的适当划分会产生 $M^\#$ 之外的 Bent 函数。
- $\ell$ -最优函数： 综述讨论了具有最小线性指数 ($ind(f)=1$) 的函数，指出它们是 Maiorana-McFarland 函数的“对立面”。文中强调了利用具有性质 (P1)（二阶导数不为零）的置换进行构造，是生成此类函数的一种方法。
M-子空间与次级构造：
- 本文对 M-子空间进行了深入的代数与组合分析。它建立了极大 M-子空间数量的界限，并将它们与 Bent 函数的分类联系起来。
- 文中给出了次级构造（直接和、间接和、2-拼接和 4-拼接）导致产生 $M^\#$ 之外函数的充要条件。值得注意的是，本文证明了将一个位于 $M^\#$ 之外的 Bent 函数与任意一个 Bent 函数进行 4-拼接，会得到一个新的位于 $M^\#$ 之外的 Bent 函数。

意义
本文旨在通过建立一个综合性的框架，连接研究透彻的 Maiorana-McFarland 类与庞大且在很大程度上尚未分类的 Bent 函数空间。其主要意义在于：

系统化排除过程： 提供了一个统一的框架，用于判定 Bent 函数何时落在 $M^\#$ 之外，从而超越了基于经验的个案，转向基于线性指数和 M-子空间的结构化刻画。
扩展构造方法： 详细阐述了生成 $M^\#$ 之外无限 Bent 函数族的显式方法（C, D, $P_\tau$ , GMM），解决了固定维度下已知示例稀缺的问题。
澄清代数结构： 引入并完善了线性指数和 M-子空间等概念，将其作为理解 Bent 函数及其与广义 Maiorana-McFarland 层级关系的根本工具。
明确开放问题： 论文最后列出了众多开放性问题，包括 $M^\#$ 中 EA-等价类的精确计数、将这些理论扩展到 $p$ 进制 Bent 函数，以及在 McFarland 类之外构造差集。

作者保持了谦逊的态度，承认尽管在识别 $M^\#$ 之外的函数方面已取得显著进展，但 Bent 函数的总数统计以及对其代数结构的完整分类仍然是悬而未决的挑战。这项工作为旨在设计具有特定非线性性质（且无法通过标准 Maiorana-McFarland 构造捕获）的密码学重要布尔函数的学者提供了基础性参考。

类似论文