🔢 mathematics

On the Walsh spectra of quadratic APN functions

本文建立了二次 APN 函数的 Walsh 谱与射影空间中的向量空间划分或阻塞集之间的新颖联系，从而能够推导出强有力的谱条件，例如对高振幅分量函数的限制、对弯曲分量的非平凡上界以及关于 CCZ-等价于置换的判据。

原作者： Sophie Hannah Bénéteau, Nicolas Goluboff, Lukas Kölsch, Divyesh Vaghasiya

发布于 2026-05-19

📖 1 分钟阅读🧠 深度阅读

原作者： Sophie Hannah Bénéteau, Nicolas Goluboff, Lukas Kölsch, Divyesh Vaghasiya

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

想象你正在设计一个高安全性的金库（分组密码）来保护数字秘密。为了让这个金库坚不可摧，你需要在其中安装一种特殊的“锁”。在密码学世界中，这些锁被称为APN 函数的数学函数。

将 APN 函数想象成一把主钥匙，它能将数据完美地扰乱，以至于即使窃贼试图通过比较两把略有不同的钥匙（即“差分攻击”）来猜测锁的工作原理，他们也绝对得不到任何有用的信息。这些函数是安全性的黄金标准。

然而，并非所有的锁都是生而平等的。有些是“二次”的（数学上更简单，更容易研究），而本文的研究人员正试图理解这些特定锁的内部“指纹”。

以下是本文的发现，通过日常类比进行解释：

1. 指纹：沃尔什谱（Walsh Spectrum）

每把锁都有一个独特的“指纹”，称为沃尔什谱。你可以将其视为一份成绩单，用来衡量这把锁有多“线性”或可预测。

目标：我们希望锁尽可能不可预测。
指标：本文考察了锁的不同部分的“幅度”。想象锁是由许多小齿轮（分量函数）组成的。有些齿轮转动平滑（低幅度），而有些齿轮则颠簸且嘈杂（高幅度）。研究人员想知道：一把安全的锁在变得脆弱之前，最多可以拥有多少个“嘈杂”的齿轮？

2. 第一个发现：“房间分区”类比

作者发现这些数学锁与划分房间之间存在惊人的联系。

想象锁运作的空间是一个充满点（向量）的巨大房间。研究人员证明，“嘈杂的齿轮”（锁中具有高幅度的部分）迫使房间被划分为特定的、互不重叠的子房间（向量空间）。

规则：房间中的每个点必须恰好属于一个子房间，且除了中心点外，任何两个子房间都不能共享任何空间。
洞察：这不仅仅是随机的划分。这些子房间的大小直接与齿轮有多“嘈杂”（高幅度）相关。如果你知道房间是如何划分的，你就知道了锁的指纹。

这意味着：他们证明，一把安全的锁最多只能拥有一个极其“嘈杂”的齿轮（幅度超过某个阈值）。如果它有两个，房间就无法正确划分，锁将无法通过安全测试。

3. 第二个发现：“交通堵塞”类比

本文还考察了“安静齿轮”（弯曲分量）与“嘈杂齿轮”之间的关系。他们发现，嘈杂的齿轮在几何景观中形成了一种特殊的交通堵塞（即“阻塞集”）。

类比：想象一个城市网格，其中某些十字路口被封锁。“阻塞集”是一组被封锁的十字路口，使得你尝试行驶的任何一条直路都会至少经过一个被封锁的十字路口。
发现：研究人员发现，对于这些二次锁，“嘈杂的齿轮”形成的交通堵塞非常具体。这不仅仅是任何堵塞；这是一种在任何道路上被封锁的十字路口数量始终为奇数的堵塞。
结果：这个“奇数规则”使他们能够对锁可以拥有的安静齿轮（弯曲分量）的数量设定严格的限制。这是首次为这类锁设定了该数量的通用“上限”。

4. 综合整体：“蓝图”检查

通过结合“房间分区”和“交通堵塞”规则，作者创建了一个强大的检查清单。

他们选取了特定尺寸（维度 6、8 和 10）的锁，并列出了理论上可能存在的每一种“蓝图”（幅度分布）。
然后，他们应用新规则划掉了不可能的蓝图。
示例：对于尺寸为 8 的锁，理论上存在许多排列齿轮的方式。他们的数学证明显示，许多这样的排列是不可能的，因为它们会破坏“房间分区”或“交通堵塞”规则。这显著缩小了可能存在的安全锁的列表。

5. “置换”之谜

最后，本文触及了一个著名的未解之谜：这些锁能否被重新排列成完美的“置换”（即一对一映射，每个输入都有唯一的输出，就像完美地洗一副牌）？

作者发现，如果一把锁与完美洗牌是 CCZ 等价的（一种特定的数学相似性），那么它就不能拥有“少量”的嘈杂齿轮。它必须拥有特定且大量的嘈杂齿轮。这为密码学家提供了一种新方法，来测试一把锁是否可能成为完美的洗牌。

“开放问题”总结

本文最后承认，虽然他们为可能的锁构建了更好的围栏，但尚未找到所有的锁。

他们拥有尺寸为 8 的锁的理论蓝图列表，但尚未找到所有这些蓝图对应的实际实例。
他们向数学界提问：“你能构建一把符合我们发现的那些特定、罕见的蓝图的锁吗？”

简而言之：本文并没有发明一把新锁，但它构建了一个更强大的蓝图扫描仪。它利用几何学（房间分区和交通堵塞）来立即告诉你哪些安全锁的数学设计是不可能的，从而缩小了对完美、坚不可摧的数字金库的搜索范围。

技术摘要：关于二次 APN 函数的 Walsh 谱

问题陈述
几乎完美非线性（APN）函数是对称密码系统中的关键组件，提供对差分攻击的最优抵抗性。这些函数的一个基本属性是其线性度，该属性由其 Walsh 谱决定。虽然二次 APN 函数的幅度分布（从而其 Walsh 谱）在奇数维度 $n$ 下已得到完全刻画，但偶数 $n$ 的情况在很大程度上仍属未解之谜。目前针对偶数 $n$ 的唯一已知通用约束源自 Walsh 变换的四阶矩。本文旨在填补理解二次 APN 函数 $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ （其中 $n$ 为偶数）可能 Walsh 谱的空白，具体寻求推导其幅度分布的更强条件。

方法论
作者建立了二次 APN 函数与有限几何之间的两个新颖几何联系：

向量空间划分：论文证明，二次 APN 函数的幅度分布唯一对应于环境空间 $\mathbb{F}_2^n$ 的向量空间划分。具体而言， $F$ 的非平凡非弯曲分量函数与划分中的子空间相关联，其中每个子空间的维度直接关联于相应分量函数的幅度。
阻塞集：非平凡非弯曲分量集合，记为 $N_F$ ，被证明在射影空间 $PG(n-1, 2) $中形成一种特定类型的阻塞集。关键在于，作者证明了$ N_F $与任何维度为$ n/2$ 的子空间的交集必须包含奇数个点。

通过利用关于向量空间划分和阻塞集的既定定理（特别是关于划分的“尾部”和最小阻塞集的结果），作者将这些几何约束转化为二次 APN 函数幅度分布的代数界限。

主要贡献与结果

与向量空间划分的联系（第二部分）：
- 定理 II.4 确立，如果分量函数 $F_b$ 的幅度为 $2^{(n+k)/2}$ ，则它对应于 $\mathbb{F}_2^n$ 的向量空间划分中一个维度为 $k$ 的子空间。
- 这种联系使得可以应用划分理论中的打包条件和维度界限。
- 定理 II.10：二次 APN 函数最多只能拥有一个幅度大于 $2^{3n/4}$ 的分量函数。如果存在这样的分量，则所有其他分量的幅度必须至多为 $2^{(2n-l)/2}$ ，其中 $l$ 是最大幅度的指数。
- 命题 II.14–II.16：基于线性度以及特定幅度的存在性，推导出了非弯曲分量数量（ $|N_F|$ ）的新下界。
与阻塞集的联系（第三部分）：
- 推论 III.3：集合 $N_F$ 是 $PG(n-1, 2) $中关于$ (n/2) $-空间的阻塞集，且具有额外性质：每个此类空间与$ N_F$ 的交集包含奇数个点。
- 定理 III.9：这是针对二次 APN 函数的弯曲分量数量的第一个非平凡且通用的上界。具体而言，对于 $n \ge 6$ ，非弯曲分量的数量满足 $|N_F| \ge 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ 。等式成立仅当 $n=8$ 时可能。因此，弯曲分量的数量至多为 $2^n - 2^{n/2} - 2^{n/2-2} - 2^{n/2-3}$ 。
综合与维度分析（第四部分）：
- 通过结合划分和阻塞集约束，作者排除了几种理论上可能的幅度分布。
- 定理 IV.1：类型为 $[(n/2)^{2^{n/2+1}}]$ 的向量空间划分（即 $(n/2)$ -铺展）不对应任何二次 APN 函数。
- 定理 IV.5：对于 $n=8$ ，论文将可能的幅度分布缩小到特定列表（排除平凡划分和 4-铺展），将潜在扩展 Walsh 谱的数量减少至最多 18 种不同类型。
- 命题 IV.4：论文比较了在不同参数范围内推导出的关于 $|N_F|$ 的下界的强度，确定了哪种界限取决于函数的线性度而占主导地位。
等价性与置换（第五部分）：
- 论文分析了这些结构在 EA-等价和 CCZ-等价下的行为。
- 推论 V.6：如果一个二次 APN 函数 CCZ-等价于一个置换，则它不能拥有少量的非弯曲分量；具体而言， $|N_F| \ge 3(2^{n/2}-1)$ ，且 $N_F$ 必须是一个 3-重阻塞集。

意义与主张
本文声称提供了关于二次 APN 函数 Walsh 谱的首个通用条件，超越了众所周知的四阶矩界限。通过将这类函数的代数性质与向量空间划分和阻塞集的组合结构联系起来，作者推导出了对可能幅度分布的强约束。

作者明确指出，他们的结果：

证明了二次 APN 函数最多只能拥有一个幅度大于 $2^{3n/4}$ 的分量。
提供了关于弯曲分量数量的第一个非平凡上界。
提供了基于弯曲分量数量判断函数是否 CCZ-等价于置换的条件。
系统地列出了小偶数维度（特别是 $n=6, 8, 10$ ）下所有可能的幅度分布，突出了哪些已实现以及哪些仍属未解问题。

论文最后列出了未解决问题，包括维度 8 中具有特定幅度分布的 APN 函数的存在性，以及寻找具有非经典 Walsh 谱的二次 APN 函数无限族的研究。作者保持了谦逊的语气，指出虽然他们排除了许多可能性，但二次 APN 函数 Walsh 谱的完整分类仍然是一个开放的挑战。