Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers

この論文は、有限体上のベクトル関数のほとんどが自明な拡張アフィン安定化群を持つことを証明し、これにより EA 同値性のクラス数が単純な推定値に漸近的に一致することや、ランダムな関数が EA 同値となる確率が超指数関数的に小さいことを示し、暗号原語設計におけるランダムサンプリング戦略の有効性を裏付けている。

要約

この論文は、暗号技術の核心にある「数式（関数）」の不思議な性質について、非常に驚くべき発見を報告しています。専門用語をすべて捨て、**「巨大な迷路」と「鏡」**の物語として説明しましょう。

1. 舞台設定：暗号の「鍵」となる関数たち

まず、現代の暗号（スマホの通信やクレジットカードの暗号化など）では、**「S ボックス」**と呼ばれる小さな変換装置が使われています。これは、入力された数字を別の数字に置き換える「関数」です。

この関数には、ハッキング（解読）に強い「良い性質」が必要です。しかし、同じような性質を持つ関数は無数に存在します。そこで研究者たちは、**「本質的に同じもの」**をグループ分けして、どれくらい「異なる」関数があるのかを数えようとしています。

ここで登場するのが**「EA 同値（Extended-Affine Equivalence）」**というルールです。

• イメージ： 関数 F を「料理」だとします。
• EA 同値： 食材の入れ替え（入力側の操作）や、味付けの変更（出力側の操作）をしても、料理の「本質的な味（暗号の安全性）」が変わらなければ、それは「同じ料理」とみなします。

2. 問い：「同じ料理」はどれくらいあるのか？

研究者たちは長年、2 つの大きな疑問を抱えていました。

1. 分類問題： 「本質的に異なる料理（関数）」は、結局何種類あるのか？
2. サンプリング問題： 偶然に良い料理（暗号に強い関数）を探すために、ランダムにレシピを作ったとき、「同じ料理」を何度も作ってしまわないか？（無駄な繰り返しがないか？）

これに答えるために、論文は**「鏡」**というメタファーを使います。

3. 核心発見：「鏡」を持つ関数は、ほとんど存在しない

関数には、自分自身を「鏡」のように映し返す性質を持つものがあります。これを**「安定化群（Stabilizer）」**と呼びます。

• 鏡を持つ関数： 食材を入れ替えても、味付けを変えても、**「全く同じ料理」**になってしまう関数。つまり、自分自身と「同じ」になる変換が、自分の中に隠れている状態です。
• 鏡を持たない関数： 少しでも変えれば、必ず「違う料理」になる関数。

この論文の最大の発見は以下の通りです。

「関数という宇宙には、無数の星（関数）がある。しかし、その中で『鏡（自分自身と変わらない変換）』を持っている星は、宇宙全体から見れば『奇跡的に稀』な存在だ。ほぼ 100% の関数は、鏡を持たない（自明な安定化群を持つ）。」

創造的なアナロジー：「巨大な迷路と道しるべ」

想像してください。

• 関数の世界は、広大すぎる**「迷路」**です。
• EA 同値は、迷路の中で「同じ場所」を指し示す**「道しるべ」**のルールです。
• **鏡（安定化群）を持つ関数は、「自分自身を起点にして、ぐるぐる回っても同じ場所に戻ってしまう」**という、迷路の中心にある特殊なポイントのようなものです。

論文はこう言っています：
「迷路の広さが無限に広がると、『ぐるぐる回っても同じ場所』という特殊なポイント（鏡を持つ関数）は、砂漠の砂粒の中でダイヤモンドを見つけるくらいに希少になる。ほとんどすべての関数は、少し動けば必ず『新しい場所（異なる同値クラス）』へ移動してしまう。」

4. この発見が意味すること

この「鏡はほとんどない」という事実が、2 つの重要な結論をもたらします。

① 分類の答え：「単純な計算」で正解が出る

これまでは、「本質的に異なる関数」の数を正確に数えるのは、鏡（特殊な性質）の存在を考慮しないといけないため、非常に複雑で難解でした。
しかし、「鏡を持つ関数はほぼゼロ」なので、**「総数 ÷ ルールの数」**という、小学生でもわかるような単純な計算で、ほぼ正確な答えが出ることが証明されました。

• 結論： 暗号に使える「本質的に異なる関数」の数は、単純な割り算でほぼ正確に予測できる。

② サンプリングの答え：「偶然」は最強の戦略

「良い暗号（APN 関数など）」を探すために、コンピューターでランダムに関数を作ったとします。

• 昔の心配： 「同じような関数（鏡を持つ変換）を何度も作って、時間だけ無駄にしていないか？」
• 新しい結論： 「鏡」は存在しないので、ランダムに作った 2 つの関数が、偶然『同じ料理（EA 同値）』になる確率は、宇宙の年齢よりも長い時間がかかるほど低い（超指数関数的に小さい）。

つまり、「ランダムに探す」という方法は、無駄な重複を一切気にせず、非常に効率的であることが証明されました。

まとめ：この論文のメッセージ

この論文は、複雑な数学の世界で、**「偶然の力」**の凄さを証明しました。

• 難しい問題： 「暗号の関数を分類するのは大変だ！」
• 解決策： 「実は、特殊な例外（鏡）はほとんど存在しないから、単純に考えれば OK だ！」
• 実用性： 「ランダムに試行錯誤するだけで、無駄なく新しい暗号が見つかる。安心してください！」

つまり、暗号設計において「偶然のサンプリング」は、単なる運試しではなく、数学的に裏付けられた**「最も賢い戦略」**であることが示されたのです。

技術概要

論文「Almost All Vectorial Functions Have Trivial Extended-Affine Stabilizers」の技術的サマリー

1. 概要と背景

本論文は、有限体上のベクトル値関数（Vectorial Functions）における**拡張アフィン同値（Extended-Affine equivalence: EA-equivalence）**の安定化群（Stabilizer）の構造と、その同値類の数の漸近的な挙動について研究したものです。

対称鍵暗号（ブロック暗号やハッシュ関数）において、S-Box として機能するベクトル値ブール関数の分類は極めて重要です。EA 同値性は、差分一様性（Differential Uniformity）や Walsh スペクトル、代数的次数といった重要な暗号学的性質を保存するため、暗号設計において関数を分類する際の基本的な関係性として用いられています。

従来の研究では、特定の暗号学的性質を持つ関数（APN 関数や AB 関数など）の構造や、同値判定アルゴリズムに焦点が当てられてきましたが、**「ランダムに選択された関数が EA 同値になる確率」や「EA 同値類の総数」**に関する一般的な漸近的な性質については、安定化群の計算が困難であるため未解明な部分がありました。

2. 解決すべき問題

論文は以下の 2 つの根本的な問いに答えることを目的としています。

1. 分類問題（Classification）: EA 同値類はいくつ存在するか？
   • 暗号学的に本質的に異なる関数の数を把握することは、暗号プリミティブの多様性を理解する上で不可欠です。
2. ランダムサンプリングの有効性（Random Sampling）:
   • 望ましい性質を持つ関数をランダムに生成して探索する際、EA 同値な関数が重複してサンプリングされるリスクはどの程度か？
   • 同値類の空間を効率的に探索できるのか、それとも衝突（Collision）が探索を制限するのか？

これらは、関数の EA 安定化群（StabΓ(F)）の構造に密接に関連しています。軌道・安定化群の定理（Orbit-Stabilizer Theorem）によれば、同値類のサイズは安定化群のサイズに反比例します。したがって、安定化群が自明（単位元のみ）であるかどうかが、同値類の数や衝突確率を決定づけます。

3. 手法と主要な理論的枠組み

3.1 数学的枠組み

• 対象: 有限体 $\mathbb{F}_q$ 上のベクトル空間 $U = \mathbb{F}_q^n$ から $W = \mathbb{F}_q^m$ への関数全体の集合 $\mathcal{F}$。
• 群作用: EA 群 $\Gamma = \text{AGL}(U) \times \text{AGL}(W)$ が $\mathcal{F}$ に作用します。作用は $(A_{out}, A_{in}) \cdot F = A_{out} \circ F \circ A_{in}$ で定義されます。
• 安定化群: $F$ の EA 安定化群は、$A_{out} \circ F \circ A_{in} = F$ を満たすすべての $(A_{out}, A_{in})$ の集合です。

3.2 主要な証明戦略

著者は、**「ほぼすべての関数が自明な EA 安定化群を持つ」**ことを示すことで、上記の問題を解決しました。証明の核心は以下のステップで構成されています。

1. 固定点の個数の評価（Lemma 3.3）:
   • $\Gamma$ の非自明な元 $g$ に対して、$g \cdot F = F$ となる関数 $F$ の個数 $|\text{Fix}(g)|$ を評価します。
   • アフィン置換の軌道構造（Lemma 3.1, 3.2）を用いることで、$|\text{Fix}(g)|$ が全関数数 $|\mathcal{F}|$ に比べて指数関数的に小さいことを示します。具体的には、$|\text{Fix}(g)| \le q^{c m q^n}$ （$c < 1$）という上界が導かれます。
2. 確率論的評価（Theorem 3.4）:
   • ユニオンバウンド（Union Bound）を用いて、少なくとも 1 つの非自明な元が $F$ を固定する確率を評価します。
   • 群のサイズ $|\Gamma|$ は $q^{O(n^2+m^2)}$ 程度ですが、固定点を持つ関数の割合は $q^{-(1-c)m q^n}$ 程度で減少するため、$n$ が大きくなるにつれてこの確率は**超指数関数的（super-exponentially）**に 0 に収束します。
3. Burnside の補題の応用（Corollary 3.7）:
   • 安定化群が自明である関数が圧倒的多数を占めるという結果を Burnside の補題に適用し、EA 同値類の総数が「全関数数 ÷ 群のサイズ」という単純な推定値（Naive Estimate）に漸近的に一致することを証明します。

4. 主要な結果

4.1 自明な安定化群の存在（Theorem 3.4）

• 結果: 一様ランダムに選ばれたベクトル値関数 $F$ について、非自明な EA 安定化群を持つ確率は $q^{-\Omega(m q^n)}$ 以下です。
• 意味: 暗号で用いられるような次元（例：8 ビット S-Box, $n=m=8$）において、非自明な EA 安定化群を持つ関数は、関数空間全体に対して指数関数的に希薄な部分集合です。

4.2 EA 同値類の数の漸近公式（Corollary 3.7）

• 結果: EA 同値類の数は、以下の式で与えられます。
  $$|\mathcal{F}/\Gamma| = \frac{|\mathcal{F}|}{|\Gamma|} (1 + o(1))$$
• 意味: 安定化群が自明であることが高確率で成立するため、同値類の数は「全関数数」を「群のサイズ」で割った単純な計算値と、相対誤差が 0 に収束する形で一致します。これは、Hou や Lu らによる従来の結果を、より直感的な確率論的証明によって再確認し、その背後にある構造的な理由（安定化群の自明性）を明らかにしたものです。

4.3 衝突確率の厳密な評価（Proposition 3.8, Corollary 3.9）

• 結果: 独立に一様ランダムに選ばれた 2 つの関数 $F, G$ が EA 同値である確率は、
  $$P(F \sim_{EA} G) = \frac{|\Gamma|}{|\mathcal{F}|} (1 + o(1))$$
  となります。
• 意味: この確率は超指数関数的に小さく（例：8 ビット S-Box の場合 $2^{-1900}$ 程度）、ランダムサンプリングによる探索において、EA 同値な関数が重複して見つかる可能性は実質的にゼロです。

5. 意義と応用

1. 暗号プリミティブ設計におけるランダムサンプリングの正当化:
   • APN 関数や AB 関数など、特定の暗号学的性質を持つ関数を探索する際、ランダム生成戦略が有効であることを理論的に裏付けました。EA 同値による冗長性を気にせず、効率的に探索空間を網羅できることが示されました。
2. 関数空間の構造理解:
   • 非自明な EA 安定化群を持つ関数は、関数空間全体の中で「例外（Exponential Rare Subset）」であり、一般的な関数は自明な安定化群を持つことが示されました。これは、特定の対称性を持つ関数が極めて稀であることを意味します。
3. CCZ 同値への示唆:
   • 本論文では EA 同値に焦点を当てていますが、より一般的な CCZ 同値（Carlet-Charpin-Zinoviev equivalence）についても衝突確率の上界を示しました。CCZ 同値における安定化群の自明性については今後の課題ですが、本結果はその基礎となる重要なステップです。

6. 結論

本論文は、有限体上のベクトル値関数において、**「ほぼすべての関数が自明な EA 安定化群を持つ」**という強力な漸近的性質を証明しました。これにより、EA 同値類の数が単純な推定値に収束すること、およびランダムサンプリングによる暗号関数の探索が EA 同値の観点から極めて効率的であることが数学的に確立されました。これらの結果は、対称鍵暗号の設計と解析における理論的基盤を強化するものです。