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

二次APN関数のWalsh スペクトラについて

基本情報

論文ID: 2510.12008
タイトル: On the Walsh spectra of quadratic APN functions
著者: Sophie Hannah Bénéteau（フロリダ大学）、Nicolas Goluboff（マサチューセッツ大学アマースト校）、Lukas Kölsch（南フロリダ大学）、Divyesh Vaghasiya（南フロリダ大学）
分類: math.CO cs.IT math.IT
発表日: 2025年10月15日（arXiv プレプリント）
論文リンク: https://arxiv.org/abs/2510.12008

要約

APN（Almost Perfect Nonlinear、ほぼ完全非線形）関数はブロック暗号設計において中核的な役割を果たし、差分攻撃に対する最適な耐性を提供する関数である。APN関数の最も重要な性質の一つはその線形度であり、これは関数のWalshスペクトラと直接関連している。本論文は、二次APN関数のWalshスペクトラの強い条件を導出することを可能にする2つの新規な関連性を確立している。論文は、 $n=2k$ ビット上で動作する二次APN関数 $F$ のWalsh変換が、 $\mathbb{F}_2^n$ のベクトル空間分割および対応する射影空間 $PG(n-1,2)$ における特定のブロッキング集合と一意に関連付けられることを証明している。これらの関連性により、 $F$ のWalshスペクトラに関する複数の結果を証明することが可能になり、例えば $F$ が $2^{\frac{3}{4}n}$ より大きい振幅を持つ成分関数を最大1つしか持つことができないことを証明し、二次APN関数の曲がった成分関数の数に関する初の非自明な上界を見つけている。

研究背景と動機

問題の重要性

暗号学的応用: APN関数は対称暗号システム設計における中核的な構成要素であり、特にブロック暗号の置換置換ネットワーク(SPN)において差分攻撃に対する最適な耐性を提供する。
理論的課題: 奇数次元における二次APN関数の振幅分布は完全に決定されている（すべての非自明な成分が振幅 $2^{\frac{n+1}{2}}$ を持つ）が、偶数次元の場合は依然として未解決問題である。
既存の限界:
- 偶数 $n$ に対して、振幅に関する唯一の既知制約はWalsh変換の4次モーメント特性から得られる
- 二次APN関数の曲がった成分関数の数に関する非自明な界限が欠落している
- Walshスペクトラ構造の深い理解が不足している

研究動機

本論文は、二次APN関数と幾何学的対象（ベクトル空間分割とブロッキング集合）との間に新規な関連性を確立することにより、そのWalshスペクトラの構造的性質を深く理解し、より強い制約条件を導出することを目指している。

核心的貢献

ベクトル空間分割関連性の確立: 二次APN関数 $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ （ $n$ は偶数）の振幅分布と $\mathbb{F}_2^n$ のベクトル空間分割との間の一意対応関係を証明した。
ブロッキング集合理論の構築: 非自明な非曲がった成分関数集合 $N_F$ が射影空間 $PG(n-1,2)$ において特殊なブロッキング集合を形成することを証明した。
新規制約条件の導出:
- $F$ が $2^{\frac{3}{4}n}$ より大きい振幅を持つ成分関数を最大1つしか持つことができないことを証明した
- 曲がった成分関数の数に関する初の非自明な上界を確立した
- 関数がCCZ等価で置換であるための必要条件を提供した
小次元分析の完成: 次元6、8、10の場合について完全な分析を実施し、すべての可能な振幅分布を決定した。

方法の詳細説明

タスク定義

二次APN関数 $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ （ $n$ は偶数）のWalshスペクトラ構造を研究する。ここで：

入力: 二次APN関数 $F$
出力: Walshスペクトラの制約条件と構造的性質
目標: 振幅分布の可能性と制限を理解する

中核理論フレームワーク

1. ベクトル空間分割理論

差分関数の定義: 非零 $a \in \mathbb{F}_2^n$ に対して、 $D_{F,a}(x) = F(x) + F(x+a)$ と定義する。

ベクトル空間の構築: 以下を定義する

$T_b = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = H_b\} \cup \{0\}$
$\overline{T_b} = \{a \in \mathbb{F}_2^n : \text{Im}(D_{F,a}) = \overline{H_b}\}$
$V_b = T_b \cup \overline{T_b}$

ここで $H_b = \{x \in \mathbb{F}_2^n : \langle b,x \rangle = 0\}$ である。

主定理（定理2.4）: $F_b$ の振幅は $2^{\frac{n+\dim(V_b)}{2}}$ である。

2. ブロッキング集合理論

ブロッキング集合の性質: 非自明な非曲がった成分関数集合 $N_F$ は $PG(n-1,2)$ において $(n/2)$ -空間に関するブロッキング集合を形成し、各 $(n/2)$ -空間との交集合のサイズは奇数である。

主要結果: Govaerts-Stormeの定理を最小非自明ブロッキング集合のサイズに関して利用することで、曲がった成分関数の数に関する上界を得る。

技術的革新点

幾何学化手法: 二次APN関数のWalshスペクトラ問題を初めてベクトル空間分割とブロッキング集合の幾何学的問題に変換した。
構造的特性化: $\dim(V_b)$ を通じて成分関数 $F_b$ の振幅を直接決定し、代数構造と周波数特性の直接的な関連性を確立した。
学際的応用: 有限幾何におけるベクトル空間分割とブロッキング集合の深層理論を巧妙に適用した。

実験設定

理論検証方法

本論文は主に理論研究であり、以下の方法で結果を検証している：

小次元の完全分析:
- 次元6: すべての可能なベクトル空間分割タイプが既知の二次APN関数に対応することを検証した
- 次元8: 18種類の可能な振幅分布を決定した
- 次元10: 理論上可能なすべての場合を分析した
既知関数の検証:
- 古典的Walshスペクトラ関数の検証
- 最大線形度関数の分析
- $x^3$ 関数のブロッキング集合性質の検証

計算ツール

論文は計算機支援検証を使用して以下を実施した：

小次元の場合におけるすべての可能なベクトル空間分割の列挙
理論結果と既知APN関数の一貫性の検証

実験結果

主要理論結果

1. 振幅制約（定理2.10）

結果: $n$ を偶数、 $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ を二次APN関数、線形度 $L(F) = 2^{\frac{n+l}{2}}$ で $l > n/2$ とすると：

$F$ は正確に1つの振幅 $2^{\frac{n+l}{2}}$ を持つ成分関数を持つ
他のすべての成分の振幅は最大 $2^{\frac{2n-l}{2}}$ である
特に、任意の二次APN関数は $2^{\frac{3n}{4}}$ より大きい振幅を持つ成分関数を最大1つしか持たない

2. 曲がった成分関数の上界（定理3.9）

結果: $n \geq 6$ を偶数、 $F: \mathbb{F}_2^n \to \mathbb{F}_2^n$ を二次APN関数とすると： $|N_F| \geq 2^{n/2} + 2^{n/2-2} + 2^{n/2-3} - 1$ ここで等号は $n=8$ の場合にのみ成立する可能性がある。

3. 次元8の完全分類（定理4.5）

$F: \mathbb{F}_2^8 \to \mathbb{F}_2^8$ の二次APN関数に対して、可能な振幅分布は：

$[0^{190}, 2^{64}, 6^1]$
$[0^{238-4i}, 2^{5i}, 4^{17-i}]$ 、ここで $1 \leq i \leq 17$

アブレーション分析

1. 界限の比較（命題4.4）

$|N_F|$ の3つの異なる下界を比較した：

ベクトル空間分割界限: $k < n/2$ の場合に最強
ブロッキング集合界限: $k = n/2$ の場合に最強
次元界限: $k > n/2$ の場合に最強

2. 等価性分析

EA等価下で以下を証明した：

ベクトル空間分割は等価性を保持する（定理5.2）
ブロッキング集合は等価性を保持する（定理5.1）

重要な発見

構造的制約: 二次APN関数のWalshスペクトラは厳密な幾何学的制約を受け、任意ではない。
次元効果: 次元が増加するにつれて、可能な振幅分布は急速に減少する。
CCZ等価条件: 二次関数がCCZ等価で置換である場合、 $|N_F| \geq 3(2^{n/2} - 1)$ である。

結論と議論

主要結論

二次APN関数のWalshスペクトラは深層の幾何学的構造を持つ
ベクトル空間分割とブロッキング集合はWalshスペクトラの理解のための強力なツールを提供する
理論上可能な振幅分布の大部分は実際には実現できない

限界

構成的問題: 理論は多くの可能性を排除するが、新しい構成方法は提供していない
次元制限: 主要結果は偶数次元に集中している
計算複雑性: 高次元の場合の完全な分析は依然として困難である

今後の方向

論文は6つの開放問題を提起しており、以下を含む：

次元8で欠落している振幅分布の例を見つける
$|N_F|$ の界限を改善する
より多くの実現不可能なベクトル空間分割タイプを見つける

深度評価

利点

理論的革新性: Walshスペクトラを理解するための全く新しい幾何学的視点を確立した
方法の体系性: ベクトル空間分割とブロッキング集合の2つの角度から体系的に研究した
結果の深刻性: 複数の初の非自明な界限を得た
分析の完全性: 小次元の場合について詳細な分析を実施した

不足

構成の欠落: 主に排除的結果であり、新しいAPN関数の構成が欠落している
計算検証: 一部の結果は計算機検証に依存しており、理論的証明が不完全である
応用の限界: 主に理論的貢献であり、実際の暗号学的応用価値は検証が必要である

影響力

学術的価値: APN関数理論に新しい研究ツールと視点を提供した
方法論的貢献: 幾何学化手法は他の暗号学的問題の研究に着想を与える可能性がある
開放問題: 提起された問題は後続研究の方向を示している

適用シーン

二次APN関数の理論分析
暗号学におけるS-ボックスの設計と分析
有限幾何の暗号学への応用研究
ブール関数Walshスペクトラの構造研究

参考文献

論文は25篇の重要な文献を引用しており、APN関数理論、ベクトル空間分割、ブロッキング集合理論など複数の分野の古典的研究を網羅しており、学際的研究の特徴を示している。主要な参考文献にはCarletのブール関数専著、Govaerts-Stormeのブロッキング集合に関する研究、およびHedenらのベクトル空間分割に関する研究が含まれている。