Relative Difference sets from Almost Perfect Nonlinear Functions

この論文は、特定の 2 対 1 の Almost Perfect Nonlinear 関数の像集合が相対差集合となることを示し、Pott の結果を通じて Almost Perfect Nonlinear 関数と Bent 関数の間の新たな関連性を確立したものである。

要約

1. 物語の舞台：暗号の「最強の盾」

まず、この研究の背景にある**「APN 関数」**とは何でしょうか？

Imagine 暗号化の仕組みを、**「魔法の箱」**だと考えてみてください。この箱に数字（メッセージ）を入れると、別の数字（暗号文）が出てきます。
ハッカーは「もし、入力を変えたら、出力はどう変わるかな？」と試して、箱の仕組みを解き明かそうとします（これを「微分攻撃」と呼びます）。

• APN 関数は、この箱の中で**「最も頑丈な盾」**のような役割を果たします。
• 入力を変えても、出力の変化が予測しにくく、ハッカーが「あ、こうなったらこうなる！」とパターンを見つけられないように設計されています。
• この論文では、特に**「2 対 1（2-to-1）」**という性質を持つ APN 関数に注目しています。これは、「異なる 2 つの数字を入れると、同じ出力が返ってくる」という、少し不思議な箱です。

2. 発見：「影」が描く完璧なパズル

著者の王さんは、この「2 対 1 の魔法の箱」から出てくる数字の集まり（画像集合）を詳しく調べました。

すると、ある驚くべき事実が見つかりました。
この数字の集まりは、単なるランダムな数字の羅列ではなく、**「相対差集合（Relative Difference Set）」という、数学的に非常に整然とした「パズルのピース」**の形をしていたのです。

• アナロジー：
  Imagine 大きな正方形のタイル（全体）があり、その中に特定の色のタイル（APN 関数の出力）を配置します。
  「相対差集合」とは、**「どの 2 つのタイルを選んでも、その間の距離（差）を計算すると、特定のルールに従って、すべての距離が均等に現れる」**という、完璧にバランスの取れた配置のことです。
  • 通常、ランダムに配置すると、距離の偏りが生まれます。
  • しかし、この APN 関数から生まれた配置は、「禁止された距離（特定のタイルの差）」を除けば、すべての距離が均等に散らばっているという、驚くべき秩序を持っていたのです。

3. 意外なつながり：「曲がりくねった道」と「直線」

さらに、この研究は**「ベント関数（Bent Function）」**という別の数学の概念ともつながっていることを示しました。

• ベント関数は、暗号において「最もランダムに見える」関数として有名です。まるで**「複雑に曲がりくねった道」**のようであり、誰にも先読みができません。
• 一方、APN 関数は「盾」のような役割です。

王さんの研究は、**「この『完璧なパズル（相対差集合）』を作っている APN 関数は、実は『最もランダムな道（ベント関数）』と表裏一体の関係にある」**と証明しました。

• メタファー：
  氷山を想像してください。
  • 水面の上に突き出ているのが「APN 関数（暗号の盾）」。
  • 水面の下に隠れている巨大な氷の塊が「ベント関数（ランダム性）」。
  • この論文は、「この氷山（APN 関数）の形を調べると、実は水面下の氷（ベント関数）の形と完全に一致していることがわかった！」と言っているのです。

4. この研究の意義と「まだ解けない謎」

この発見は、暗号学者にとって非常に重要です。なぜなら、**「暗号を強くする（APN）」ことと「完全なランダム性（ベント）」**を作るための設計図が、実は同じ場所にあるかもしれないと示唆したからです。

しかし、論文の最後には**「未解決の問題」**も残されています。

• 謎： 「すべての APN 関数が、この『完璧なパズル（相対差集合）』を作ってくれるわけではない」ということがわかったのです。
• 問い： 「では、いったいどの APN 関数がパズルを作ってくれるのか？その条件は何か？」
• 問い： 「すべての『ランダムな道（ベント関数）』は、この APN 関数から作れるのか？」

まとめ

この論文は、**「暗号の最強の盾（APN 関数）」を詳しく調べることで、「数学的なパズル（相対差集合）」と「完全なランダム性（ベント関数）」**の間に、美しい橋がかかっていることを発見しました。

まるで、**「複雑な暗号の仕組みを解き明かす鍵」が、実は「数学的な美しさそのもの」**に隠されていたという、ミステリー小説のような発見です。

まだ「すべての鍵がどこにあるか」はわかりませんが、この発見は、より安全で強力な暗号システムを作るための、新しい地図を描き始めたと言えます。

技術概要

論文「Almost Perfect Nonlinear Functions からの相対差集合」の技術的サマリー

以下は、Zeying Wang 氏による論文「Relative Difference Sets from Almost Perfect Nonlinear Functions」の詳細な技術的サマリーです。

1. 研究の背景と問題設定

背景:

• APN 関数 (Almost Perfect Nonlinear Functions): 有限体 $\mathbb{F}_{2^n}$ 上の関数 $f$ において、任意の $a \neq 0, b$ に対して方程式 $f(x+a) - f(x) = b$ の解の数が最大で 2 となる関数。暗号理論、特にブロック暗号の S 箱に対する差分攻撃への耐性において極めて重要視されている。
• 相対差集合 (Relative Difference Sets, RDS): 群 $G$ の正規部分群 $N$ に対する $k$ 部分集合 $R$。$R$ 内の要素の差が、$G \setminus N$ の各要素をちょうど $\lambda$ 回、$N \setminus \{0\}$ の要素を 0 回カバーするもの。
• 既存の研究: Kolsch らの研究 [5] により、特定の APN 関数（特に $n$ が奇数の場合）の像集合が「2-to-1 写像」（各値に 2 個の原像を持つ）となることが示されている。また、著者自身の先行研究 [8] では、2-to-1 の平面関数（Planar function）の像集合が差集合や部分差集合を形成することが示されていた。

問題設定:

• 2-to-1 である平面関数の結果が APN 関数にも適用できるか？
• 特定の 2-to-1 APN 関数の像集合は、有限体上の加法群における「相対差集合」を形成するか？
• この発見は、APN 関数と Bent 関数（完全非線形関数）の間にどのような新たな関係をもたらすか？

2. 手法とアプローチ

著者は、以下の論理的枠組みを用いて問題を解決しました。

1. 像集合の特定: 既知の 2-to-1 APN 関数ファミリーの像集合 $D$ を定義する。
2. 差の計算: 像集合 $D$ から取り出された任意の 2 要素 $x_1, x_2$ の差 $b = x_1 - x_2$ が、禁止部分群 $N$ 以外の要素に対して何回現れるかを厳密に数える。
3. トレース関数の性質の活用: 有限体 $\mathbb{F}_{2^n}$ 上のトレース関数 $Tr(\cdot)$ の性質（特に $n$ が奇数の場合の $Tr(1)=1$ など）や、線形写像の性質を駆使して、方程式の解の個数を解析する。
4. Pott の定理との連結: 得られた相対差集合の結果を、A. Pott が示した「Perfect Nonlinear 関数と半正則分割差集合の同値性」の定理に適用し、そこから導かれる Bent 関数の性質を考察する。

3. 主要な貢献と結果

この論文は、以下の 3 つの主要な結果を導き出しました。

3.1. 2-to-1 APN 関数の像集合が相対差集合となることの証明

著者は、$\mathbb{F}_{2^n}$ ($n$ は奇数) 上の以下の 3 つの APN 関数ファミリーについて、その像集合が相対差集合であることを証明しました。

1. 関数 $f(x) = x + a^{-1}Tr(a^3x^3)$

   • 像集合 $D$ は、部分群 $N = \{0, a^{-1}\}$ に対する $(2^{2k}, 2, 2^{2k}, 2^{2k-1})$-相対差集合となる（ここで $n=2k+1$）。
   • この結果は、$x^3$ が置換関数となる $n$ が奇数の場合、$x^3 + a^{-1}Tr(a^3x^9)$ という APN 関数にも拡張される（定理 2.4）。
   • さらに、この関数に $\mathbb{F}_2$ 上の線形写像を合成した関数についても同様の性質が成り立つ（相対差集合の構造は保存される）。

2. 関数 $k(x) = x^6 + \alpha x^3 + \gamma Tr(\alpha^{-3}x^9 + \beta x^3)$

   • 特定の条件（$\gamma \notin \{x^2+\alpha x\}$ など）を満たすとき、この関数も 2-to-1 APN であり、その像集合は部分群 $N=\{0, \gamma\}$ に対する相対差集合となる（定理 2.7）。

3. 関数 $f(x) = x^{2^k-1} + x^{2^k}$

   • 体 $\mathbb{F}_{2^{2k-1}}$ 上で定義されるこの関数は 2-to-1 APN であり、その像集合は部分群 $N=\{0, 1\}$ に対する $(2^{2k-2}, 2, 2^{2k-2}, 2^{2k-3})$-相対差集合となる（定理 2.10）。

重要な注記:

• 著者は、すべての 2-to-1 APN 関数が相対差集合を生成するわけではないことを示した。例えば、$f(x)=x^3+x^4$ は奇数次の体で 2-to-1 APN であるが、その像集合は常に相対差集合にはならない。

3.2. Bent 関数との関係性の確立

• A. Pott の定理（Perfect Nonlinear 関数 $\iff$ 半正則分割差集合）を応用し、上記で得られた APN 関数の像集合から導かれる関数が Bent 関数であることを示した。
• 定理 3.2: $h(x) = x + a^{-1}Tr(a^3x^3)$ から導かれる Bent 関数は、アフィン同値（Affine equivalent）の範囲で、既知の二次 Bent 関数 $x_1x_2 \oplus x_3x_4 \oplus \cdots \oplus x_{n-2}x_{n-1} \oplus \epsilon$ に一致することが証明された。
• 計算実験からは、$x^{2^k-1} + x^{2^k}$ からも二次 Bent 関数が導かれる可能性が示唆されているが、厳密な証明は今後の課題とされた。

4. 意義と今後の課題

学術的意義:

• APN 関数と組合せ論的構造の橋渡し: APN 関数の像集合が相対差集合という強力な組合せ論的構造を持つことを初めて示し、暗号理論と組合せ論の深い関連性を明らかにした。
• Bent 関数への新たな視点: APN 関数（差分耐性）と Bent 関数（線形耐性）の間に、像集合の構造を通じて新たな対応関係が存在することを示唆した。
• 関数クラスの分類: すべての 2-to-1 APN 関数が相対差集合を生成するわけではないという反例を示すことで、APN 関数の内部構造の多様性と、相対差集合を生成する関数の特殊性を浮き彫りにした。

今後の課題 (Open Problems):

• 相対差集合を生成する APN 関数を特徴づける一般的な条件は何か？
• すべての APN 関数が、相対差集合を生成する APN 関数と EA 同値または CCZ 同値であるか？
• 任意の Bent 関数が、何らかの 2-to-1 APN 関数を通じて導かれるか？

結論

本論文は、特定の 2-to-1 APN 関数の像集合が相対差集合を形成することを厳密に証明し、これを通じて APN 関数と Bent 関数の間の理論的架け橋を構築しました。これは、暗号学的に重要な関数クラスの構造的理解を深め、将来の暗号設計や組合せ論的研究に重要な指針を与える成果です。