2025-11-15T00:04:11.828858

On the Walsh spectra of quadratic APN functions

Bénéteau, Goluboff, Kölsch et al.
APN functions play a central role as building blocks in the design of many block ciphers, serving as optimal functions to resist differential attacks. One of the most important properties of APN functions is their linearity, which is directly related to the Walsh spectrum of the function. In this paper, we establish two novel connections that allow us to derive strong conditions on the Walsh spectra of quadratic APN functions. We prove that the Walsh transform of a quadratic APN function $F$ operating on $n=2k$ bits is uniquely associated with a vector space partition of $\mathbb{F}_2^n$ and a specific blocking set in the corresponding projective space $PG(n-1,2)$. These connections allow us to prove a variety of results on the Walsh spectrum of $F$. We prove for instance that $F$ can have at most one component function of amplitude larger than $2^{\frac{3}{4}n}$. We also find the first nontrivial upper bound on the number of bent component functions of a quadratic APN function, and and provide conditions for a function to be CCZ-equivalent to a permutation, based on its number of bent components.
academic

On the Walsh spectra of quadratic APN functions

基本信息

  • 论文ID: 2510.12008
  • 标题: On the Walsh spectra of quadratic APN functions
  • 作者: Sophie Hannah Bénéteau (University of Florida), Nicolas Goluboff (University of Massachusetts Amherst), Lukas Kölsch (University of South Florida), Divyesh Vaghasiya (University of South Florida)
  • 分类: math.CO cs.IT math.IT
  • 发表时间: October 15, 2025 (arXiv预印本)
  • 论文链接: https://arxiv.org/abs/2510.12008

摘要

APN（Almost Perfect Nonlinear）函数在分组密码设计中扮演核心角色，是抵御差分攻击的最优函数。APN函数最重要的性质之一是其线性度，这与函数的Walsh谱直接相关。本文建立了两个新颖的联系，使我们能够推导出二次APN函数Walsh谱的强条件。论文证明了在n=2kn=2k位上操作的二次APN函数FF的Walsh变换与F2n\mathbb{F}_2^n的向量空间分拆以及相应射影空间PG(n−1,2)PG(n-1,2)中的特定阻塞集唯一关联。这些联系使得我们能够证明关于FF的Walsh谱的多项结果，例如证明FF最多只能有一个幅度大于234n2^{\frac{3}{4}n}的分量函数，并找到了二次APN函数弯曲分量函数数量的首个非平凡上界。

研究背景与动机

问题的重要性

  1. 密码学应用：APN函数是对称密码系统设计中的核心构建块，特别是在分组密码的替换置换网络(SPN)中，提供对差分攻击的最优抗性。
  2. 理论挑战：虽然奇数维情况下二次APN函数的幅度分布已被完全确定（所有非平凡分量都具有幅度2n+122^{\frac{n+1}{2}}），但偶数维情况仍然是一个开放问题。
  3. 现有局限性：
    • 对于偶数nn，目前关于幅度的唯一已知约束来自Walsh变换的四阶矩刻画
    • 缺乏对二次APN函数弯曲分量函数数量的非平凡界限
    • 对Walsh谱结构的深层理解不足

研究动机

本文旨在通过建立二次APN函数与几何对象（向量空间分拆和阻塞集）之间的新联系，来深入理解其Walsh谱的结构性质，并推导出更强的约束条件。

核心贡献

  1. 建立了向量空间分拆联系：证明了二次APN函数F:F2n→F2nF: \mathbb{F}_2^n \to \mathbb{F}_2^n（nn为偶数）的幅度分布与F2n\mathbb{F}_2^n的向量空间分拆之间的唯一对应关系。
  2. 构建了阻塞集理论：证明了非平凡非弯曲分量函数集合NFN_F在射影空间PG(n−1,2)PG(n-1,2)中形成特殊的阻塞集。
  3. 推导了新的约束条件：
    • 证明了FF最多只能有一个幅度大于234n2^{\frac{3}{4}n}的分量函数
    • 建立了弯曲分量函数数量的首个非平凡上界
    • 提供了函数CCZ等价于置换的必要条件
  4. 完成了小维度分析：对维度6、8、10的情况进行了完整分析，确定了所有可能的幅度分布。

方法详解

任务定义

研究二次APN函数F:F2n→F2nF: \mathbb{F}_2^n \to \mathbb{F}_2^n（nn为偶数）的Walsh谱结构，其中：

  • 输入：二次APN函数FF
  • 输出：Walsh谱的约束条件和结构性质
  • 目标：理解幅度分布的可能性和限制

核心理论框架

1. 向量空间分拆理论

定义差分函数：对于非零a∈F2na \in \mathbb{F}_2^n，定义DF,a(x)=F(x)+F(x+a)D_{F,a}(x) = F(x) + F(x+a)。

构造向量空间：定义

  • Tb={a∈F2n:Im(DF,a)=Hb}∪{0}T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}
  • Tb‾={a∈F2n:Im(DF,a)=Hb‾}\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}
  • Vb=Tb∪Tb‾V_b = T_b \cup \overline{T_b}

其中Hb={x∈F2n:⟨b,x⟩=0}H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}。

主要定理（定理2.4）：FbF_b的幅度为2n+dim⁡(Vb)22^{\frac{n+\dim(V_b)}{2}}。

2. 阻塞集理论

阻塞集性质：非平凡非弯曲分量函数集合NFN_F在PG(n−1,2)PG(n-1,2)中形成关于(n/2)(n/2)-空间的阻塞集，且与每个(n/2)(n/2)-空间的交集大小为奇数。

关键结果：利用Govaerts-Storme定理关于最小非平凡阻塞集的大小，得到弯曲分量函数数量的上界。

技术创新点

  1. 几何化方法：首次将二次APN函数的Walsh谱问题转化为向量空间分拆和阻塞集的几何问题。
  2. 结构性刻画：通过dim⁡(Vb)\dim(V_b)直接确定分量函数FbF_b的幅度，建立了代数结构与频谱性质的直接联系。
  3. 交叉学科应用：巧妙地应用了有限几何中向量空间分拆和阻塞集的深层理论。

实验设置

理论验证方法

本文主要是理论研究，通过以下方式验证结果：

  1. 小维度完整分析：
    • 维度6：验证了所有可能的向量空间分拆类型都对应于已知的二次APN函数
    • 维度8：确定了18种可能的幅度分布
    • 维度10：分析了所有理论上可能的情况
  2. 已知函数验证：
    • 经典Walsh谱函数的验证
    • 最大线性度函数的分析
    • x3x^3函数的阻塞集性质验证

计算工具

论文使用了计算机辅助验证来：

  • 枚举小维度情况下的所有可能向量空间分拆
  • 验证理论结果与已知APN函数的一致性

实验结果

主要理论结果

1. 幅度约束（定理2.10）

结果：设nn为偶数，F:F2n→F2nF: \mathbb{F}_2^n \to \mathbb{F}_2^n为二次APN函数，线性度L(F)=2n+l2L(F) = 2^{\frac{n+l}{2}}且l>n/2l > n/2，则：

  • FF恰好有一个幅度为2n+l22^{\frac{n+l}{2}}的分量函数
  • 所有其他分量的幅度至多为22n−l22^{\frac{2n-l}{2}}
  • 特别地，任何二次APN函数最多有一个幅度大于23n42^{\frac{3n}{4}}的分量函数

2. 弯曲分量函数上界（定理3.9）

结果：设n≥6n \geq 6为偶数，F:F2n→F2nF: \mathbb{F}_2^n \to \mathbb{F}_2^n为二次APN函数，则： ∣NF∣≥2n/2+2n/2−2+2n/2−3−1|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1 其中等号仅在n=8n=8时可能成立。

3. 维度8的完整分类（定理4.5）

对于F:F28→F28F: \mathbb{F}_2^8 \to \mathbb{F}_2^8的二次APN函数，可能的幅度分布为：

  • [0190,264,61][0^{190}, 2^{64}, 6^1]
  • [0238−4i,25i,417−i][0^{238-4i}, 2^{5i}, 4^{17-i}]，其中1≤i≤171 \leq i \leq 17

消融分析

1. 界限比较（命题4.4）

比较了三种不同的∣NF∣|N_F|下界：

  • 向量空间分拆界限：在k<n/2k < n/2时最强
  • 阻塞集界限：在k=n/2k = n/2时最强
  • 维度界限：在k>n/2k > n/2时最强

2. 等价性分析

证明了在EA等价下：

  • 向量空间分拆保持等价性（定理5.2）
  • 阻塞集保持等价性（定理5.1）

重要发现

  1. 结构性约束：二次APN函数的Walsh谱受到严格的几何约束，不是任意的。
  2. 维度效应：随着维度增加，可能的幅度分布急剧减少。
  3. CCZ等价条件：如果二次函数CCZ等价于置换，则∣NF∣≥3(2n/2−1)|N_F| \geq 3(2^{n/2} - 1)。

相关工作

主要研究方向

  1. APN函数分类：Carlet, Charpin, Zinoviev等人的工作
  2. Walsh谱理论：四阶矩方法和线性度界限
  3. 向量空间分拆：Heden, Bu等人的构造理论
  4. 阻塞集理论：Govaerts-Storme的最优界限

本文优势

  • 首次建立了Walsh谱与几何对象的直接联系
  • 提供了比经典四阶矩更强的约束条件
  • 统一了代数和几何的观点

结论与讨论

主要结论

  1. 二次APN函数的Walsh谱具有深层的几何结构
  2. 向量空间分拆和阻塞集为理解Walsh谱提供了强有力的工具
  3. 大多数理论上可能的幅度分布在实际中不能实现

局限性

  1. 构造性问题：理论排除了许多可能性，但未提供新的构造方法
  2. 维度限制：主要结果集中在偶数维度
  3. 计算复杂性：高维情况下的完整分析仍然困难

未来方向

论文提出了6个开放问题，包括：

  1. 寻找维度8中缺失幅度分布的例子
  2. 改进∣NF∣|N_F|的界限
  3. 找到更多不可实现的向量空间分拆类型

深度评价

优点

  1. 理论创新性：建立了全新的几何视角来理解Walsh谱
  2. 方法系统性：从向量空间分拆和阻塞集两个角度系统研究
  3. 结果深刻性：得到了多个首次的非平凡界限
  4. 分析完整性：对小维度情况进行了详尽分析

不足

  1. 构造缺失：主要是排除性结果，缺乏新的APN函数构造
  2. 计算验证：部分结果依赖计算机验证，理论证明不够完整
  3. 应用局限：主要是理论贡献，实际密码学应用价值有待验证

影响力

  1. 学术价值：为APN函数理论提供了新的研究工具和视角
  2. 方法论贡献：几何化方法可能启发其他密码学问题的研究
  3. 开放问题：提出的问题为后续研究指明了方向

适用场景

  • 二次APN函数的理论分析
  • 密码学中S盒的设计和分析
  • 有限几何在密码学中的应用研究
  • 布尔函数Walsh谱的结构研究

参考文献

论文引用了25篇重要文献，涵盖了APN函数理论、向量空间分拆、阻塞集理论等多个领域的经典工作，体现了跨学科研究的特点。关键参考文献包括Carlet的布尔函数专著、Govaerts-Storme关于阻塞集的工作、以及Heden等人关于向量空间分拆的研究。