Triprojective almost perfect nonlinear permutations and functions

技術的概要：三射影的ほぼ完全非線形置換と関数

問題提起
本論文は、偶数次元の有限ベクトル空間上のほぼ完全非線形（APN）置換の存在と構成に焦点を当てている。微分暗号解析の文脈において、APN 関数（微分一様性が $\Delta_F = 2$ である関数）は、置換 - 置換ネットワークにおける安全な S-Box の設計に不可欠である。APN 関数は奇数次元では存在が知られているが、偶数次元 $n > 6$ における APN 置換（全単射）の存在は依然として主要な未解決問題である。特に、著者らは $n = 3m$（$m$ は奇数）の次元においてそのような関数の大規模な族を構成し、その同値類や像集合のサイズを含む特性を特徴づけることに注力している。

手法
著者らは、「三射影的」および「半二次的」写像に基づく構造的アプローチを採用している。手法は以下の手順で進行する。

1. 射影的構造: 著者らは、$\mathbb{F}_q^3$（ただし $q=2^m$）上の関数のクラス $F \in SQH(3, q)$（半二次同次）を定義する。これらの関数は、特定の同次性を満たす半二次形式によって誘導され、射影空間 $\mathbb{P}^2(\mathbb{F}_q)$ 上で well-defined な写像を誘導することを可能にする。
2. 全単射の基準: 先行研究（定理 1.2）に依存し、特定の単変数多項式 $P(X) = aX^{\sigma^2+\sigma+1} + bX^{\sigma+1} + cX + 1$ に関する条件を用いて、射影空間上の誘導写像が全単射であることを保証する。
3. 微分一様性の解析:
   • ケース $m/d$ が偶数の場合: 著者らは関数の「コア」（微分写像が線形となる部分体）の概念を利用し、微分一様性が $2d$ であることを示す。ここで $d = \gcd(k, m)$ である。
   • ケース $m/d$ が奇数の場合: 著者らは、ねじれ多項式環（Ore 環）$\mathbb{F}_q[t; \sigma]$ の理論からの道具を導入する。多項式 $P(X)$ の根と、ねじれ環における線形右因子の存在との間の関連性を確立する。体の拡大を行い、多項式の最小共通左倍数（lclm）を解析することで、より複雑なこのケースにおいても微分一様性が $2d$ のままであることを証明する。
4. 同値性と分類: 本論文は、新しい族を既存の三変数 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)$ 対 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)$ 内で共役ではないことを示すことによって確立される。

意義と主張
本論文は、3 で割り切れるすべての奇数次元において「大規模な族」の APN 置換を提供し、偶数次元における APN 全単射という未解決問題に取り組むことを主張している。その意義は以下の点にある。

1. 一般性: この構成は、多重射影写像のクラス内で、証明可能な指数関数的な数の互いに非同値な APN 関数を生み出す。
2. 単純化: 証明は、先行研究と比較して「コンピュータを使用せず、はるかに短く、純粋に初等的」であると記述されており、さまざまな三変数 APN 関数を理解するための統一的な枠組みを提供する。
3. 新しい例: この族は、既知の APN 関数（Gold 関数を含む）と非同値な例を含んでいることが示されており、暗号プリミティブの既知の領域を拡大している。

著者らは、$m/d$ が偶数の場合の Walsh スペクトルは既知であるが、APN 置換（$m$ が奇数の場合）の Walsh スペクトルを決定することは依然として未解決問題であると指摘している。また、射影全単射をもたらす半二次同次関数の分類を、将来の研究における自然な方向性として特定している。