🔢 mathematics

Triprojective almost perfect nonlinear permutations and functions

本文引入了一类几乎完美非线性（APN）置换，适用于维度为三的奇数倍有限向量空间，同时也引入了适用于偶数维的非双射 APN 函数，所有这些函数均由一般线性群 $\mathrm{GL}(3,2^m)$ 诱导的三射影结构所刻画。

原作者： Faruk Göloğlu, Lukas Kölsch

发布于 2026-05-19

📖 1 分钟阅读🧠 深度阅读

原作者： Faruk Göloğlu, Lukas Kölsch

原始论文根据 CC0 1.0（http://creativecommons.org/publicdomain/zero/1.0/）发布到公有领域。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象你是一位试图设计终极保险箱的锁匠大师。在数字安全的世界里，“锁”是用于扰乱数据的数学函数，使黑客无法还原原始信息。你所询问的这篇论文，正是构建一种全新、极其坚固的“锁”的蓝图。

以下是作者法鲁克·格勒格鲁（Faruk Gölöglu）和卢卡斯·克尔施（Lukas Kölsch）的发现故事，解释时已去除了艰深的数学行话。

目标：完美的扰乱器

在密码学中，有一种特定类型的“锁”称为S 盒（Substitution Box，替换盒）。你可以将 S 盒想象成一台机器，它接收一组输入（例如一组数字组合），然后吐出一组完全不同的输出。

危险来自于一种称为“差分密码分析”的方法。想象一个小偷试图通过观察模式来破解你的保险箱：“如果我把拨盘向右转动一格，锁发出的声音会有特定的变化；如果转动两格，声音的变化则不同。”如果锁对微小变化的反应过于可预测，小偷就能逆向推导出密钥。

为了阻止这种情况，数学家们寻找APN 函数（Almost Perfect Nonlinear，几乎完美非线性）。这些是“完美”的锁，其中输入的微小变化会导致输出发生混乱且不可预测的变化。目标在于，无论小偷如何调整输入，输出看起来都像是随机噪声。

巨大挑战：“偶数维”问题

长期以来，数学家们知道如何为特定大小的数据构建这些完美锁（具体而言，当数据大小为奇数时）。然而，对于偶数大小的数据块（这在现实世界的计算机中非常常见），寻找一种既是完美锁又是置换（permutation，即每个输入都映射到唯一的输出，没有任何丢失）的锁，曾是一个巨大的难题。这就像试图找到一把能打开特定一排房子里所有锁的钥匙，但你总是发现有些钥匙能同时打开两把锁，或者有些锁根本没有对应的钥匙。

这篇论文的作者表示：“我们找到了一种方法，可以为一大类全新的偶数大小数据块构建这些完美且不重复的锁。”

秘密配方：“三射影”架构

作者们并非偶然发现了一个随机公式。他们使用一种特定的架构风格构建了这些锁，称之为“三射影”（Triprojective）。

要理解这一点，想象你正在观察一座三维雕塑。

标准锁：通常，这些锁是通过仅从一个角度观察雕塑构建的（即平面的、二维的视角）。
新的“三射影”锁：作者们通过同时从三个不同的角度观察雕塑来构建他们的函数，使用了一组特殊的规则（与称为 $GL(3, 2^m)$ 的数学结构相关）。

他们称之为“三射影”结构，因为它将数据视为存在于一个几何规则略有扭曲的三维空间中。通过以这种方式排列数据，他们确保了“扰乱”过程以一种极难预测的方式进行，无论你如何尝试探测它。

魔法公式

这篇论文提出了这些锁的具体配方（公式）。它涉及三个变量（ $x, y, z$ ）和一些特殊数字（ $a, b, c$ ）。

该配方包含一个“安全检查”。在使用这把锁之前，你必须运行一个快速测试，以确保某个特定方程没有解。

如果测试通过：你将获得一把完美且坚不可摧的锁（APN 置换）。
如果测试失败：这把锁仍然非常坚固（高度非线性），但它可能不是一个完美的置换（某些输入可能会映射到相同的输出）。

作者们证明，如果你正确选择数字，这个配方适用于所有能被三整除的奇数维度。这是对以往已知内容的巨大扩展。

为何这很重要（根据论文所述）

统一了旧发现：作者们表明，近年来由不同数学家发现的几个其他复杂公式，实际上只是他们新的“三射影”配方的特殊简化版本。这就像意识到三种不同类型的汽车实际上只是同一底盘上的不同喷漆。
新颖且独特：他们证明，他们新的锁族与“金”锁（Gold，几十年前发现的一类著名 APN 函数）在本质上截然不同。他们不仅仅是重新标记旧钥匙，而是在锻造全新的钥匙。
证明“干净”：以往试图证明这些锁有效的尝试需要庞大的计算机模拟和数页复杂的代数运算。作者们使用了一种巧妙的、纯逻辑的方法（利用“扭曲多项式”和有限域的性质）来证明他们的结果，而无需超级计算机。

核心结论

这篇论文是数字安全锁设计领域的数学突破。作者们发现了一种新的、通用的“三射影”方法，用于构建几乎完美非线性置换。

简单来说：他们找到了一种新的、可靠的方法，为各种计算机数据大小构建最强有力的数据扰乱器，解决了一个多年来难倒专家的问题。他们不仅找到了一把新锁，而是找到了一个制造这些锁的整个工厂，并证明了这些新锁与我们此前见过的任何锁都截然不同。

技术摘要：三投影几乎完美非线性置换与函数

问题陈述
本文探讨了偶维有限向量空间上几乎完美非线性（APN）置换的存在性与构造。在差分密码分析的背景下，APN 函数（即差分均匀性 $\Delta_F = 2$ 的函数）对于设计置换 - 置换网络中安全的 S 盒至关重要。虽然已知奇数维存在 APN 函数，但偶数维 $n > 6$ 下 APN 置换（双射）的存在性仍是一个主要的未解决问题。具体而言，作者专注于在维度 $n = 3m$ （其中 $m$ 为奇数）下构造此类函数的大规模族，并刻画其性质，包括其等价类和像集大小。

方法论
作者采用基于“三投影”和“半二次”映射的结构化方法。方法论按以下步骤进行：

投影结构：作者在 $\mathbb{F}_q^3$ （其中 $q=2^m$ ）上定义了一类函数 $F \in SQH(3, q)$ （半二次齐次）。这些函数由满足特定齐次性质的半二次型诱导，使其能在射影空间 $\mathbb{P}^2(\mathbb{F}_q)$ 上诱导定义良好的映射。
双射判据：依赖先前的工作（定理 1.2），本文利用特定单变量多项式 $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$ 上的条件，以确保射影空间上的诱导映射为双射。
差分均匀性分析：
- 情形 $m/d$ 为偶数：作者利用函数的“核心”概念（即导数映射为线性的子域），证明差分均匀性为 $2d$ ，其中 $d = \gcd(k, m)$ 。
- 情形 $m/d$ 为奇数：作者引入了扭曲多项式环（Ore 环） $\mathbb{F}_q[t; \sigma]$ 的理论工具。他们建立了多项式 $P(X)$ 的根与扭曲环中线性右因子存在性之间的联系。通过扩域并分析多项式的最小公左倍式（lclm），他们证明了即使在更复杂的情形下，差分均匀性仍保持为 $2d$ 。
等价性与分类：本文使用线性等价性将新族与现有的三元 APN 函数（特别是 Li-Kaleyski 和 Bartoli-Stanica 提出的函数）进行比较。此外，通过分析线性自同构群（ $Aut_L(F)$ ）并证明它们在一般线性群中不能共轭，证明了其与 Gold APN 函数（ $x^{2^i+1}$ ）的不等价性。

主要贡献与结果

APN 置换的构造：本文提出了针对维度 $n=3m$ （其中 $m$ 为奇数）的有限向量空间的大规模 APN 置换族。这些函数定义为：
$F(x, y, z) = (x^{\sigma+1} + ay^\sigma z + bx^\sigma y + cx^\sigma z, \quad ay^{\sigma+1} + z^\sigma x + bz^\sigma y + cx^\sigma y, \quad z^{\sigma+1} + x^\sigma y)$
其中 $\sigma = 2^k$ ， $a, b, c \in \mathbb{F}_q$ ，且 $a \neq 0$ 。
差分均匀性：作者证明，如果多项式方程 $ax^{\sigma^2+\sigma+1} + bx^{\sigma+1} + cx + 1 = 0$ 在 $\mathbb{F}_q$ 中无解，则 $F$ 的差分均匀性为 $2d$ （其中 $d = \gcd(k, m)$ ）。因此，当 $d=1$ 且 $m$ 为奇数时， $F$ 是一个 APN 置换。
像集大小：本文刻画了这些函数的像集大小。如果 $m/d$ 为偶数，该函数在 $\mathbb{F}_q^3 \setminus \{0\}$ 上是 $(2d+1)$ 对一的。如果 $m/d$ 为奇数，该函数在 $\mathbb{F}_q^3$ 上是双射。
现有族的统一：作者证明，最近发现的几个三元 APN 函数族（Li-Kaleyski 和 Bartoli-Stanica）在特定参数 $a, b, c$ 下，与其提出的族中的特定实例线性等价。这为这些构造提供了一个统一的、初等的解释，避免了先前证明中使用的复杂情形区分和计算机辅助的结果计算。
与 Gold 函数的不等价性：本文证明，对于 $m > 2$ 且 $m \neq 6$ ，构造出的 APN 函数与 Gold APN 函数是 CCZ-不等价的。这是通过证明它们的线性自同构群在 $GL(3m, 2)$ 中不共轭来确立的。

意义与主张
本文声称在每一个能被三整除的奇数维度中提供了“大规模”的 APN 置换族，解决了偶数维 APN 双射的开放性问题。其意义在于：

普遍性：该构造在多重投影映射类中产生了可证明指数级数量的两两不等价的 APN 函数。
简化：与先前的工作相比，证明被描述为“无需计算机、更短且纯粹初等”，为理解各种三元 APN 函数提供了一个统一的框架。
新实例：该族被证明包含与已知 APN 函数（包括 Gold 函数）不等价的实例，扩展了已知密码原语的范围。

作者指出，虽然 $m/d$ 为偶数的情形下的 Walsh 谱是已知的，但确定 APN 置换（其中 $m$ 为奇数）的 Walsh 谱仍然是一个未解决的问题。他们还指出，刻画导致射影双射的半二次齐次函数的分类是未来研究的一个自然方向。