Bent Functions and the Completed Maiorana-McFarland Class

技術要約：ベント関数と完成されたマイオラナ・マクファーランド・クラス

問題提起
Rothausによって導入されたブーリアン・ベント関数は、偶数変数の変数において最大非線形性（アフィン関数からの最大距離）を達成する基本的な関数のクラスを代表するものである。マイオラナ・マクファーランド（M）クラスとその完成版（$M^\#$）は、最も詳細に理解されている明示的なベント関数の族であるが、近年の計算上の証拠は、ベント関数の総数と$M^\#$に属する関数の間に顕著な乖離があることを示している。具体的には、次元8において、ベント関数の総数は約$2^{106}$であるのに対し、$M^\#$に等価な関数の数は最大でも$2^{81}$と推定されている。この観察は、本サーベイの中核的な問題、すなわち、完成されたマイオラナ・マクファーランド・クラス（$M^\#$）の外にあるベント関数の特性を明らかにし、それらの代数的構造を理解し、そのような関数の明示的な構成方法を開発することへの動機付けとなっている。本論文は、「除外問題」——様々なベント関数クラスと$M^\#$との交わりを特定し、関数がこのクラスの外にあることを証明できる条件を特定すること——に焦点を当てている。

手法
本論文は、設計および解析におけるブーリアン・ベント関数の基礎的な結果と最近の進展を統合し、包括的なサーベイ手法を採用している。技術的なアプローチは、以下の点に大きく依存している：

1. 代数的特性化： 第2次導関数基準（補題1.2）を利用して、$M^\#$への所属を特性化する。関数が$M^\#$に属するための必要十分条件は、ある$m$次元の部分空間$U$が存在し、すべての第2次導関数$D_a D_b f$が$a, b \in U$に対して消滅することである。
2. 線形指数とM-部分空間： 「線形指数」（$ind(f)$）を分析する。これは、最大となるM-部分空間（第2次導関数が消滅する部分空間）の次元として定義される。$ind(f) = n/2$である関数は$M^#$に属し、$ind(f)=1$という最小の指数を持つ関数は$\ell$-最適（$\ell$-optimal）と呼ばれる。
3. 二次的構成： 直和/間接和、連結（2連結および4連結）、およびトレース項や部分空間のインジケータの加算といった操作が、$M^\#$への所属にどのように影響するかを調査する。
4. 一般化されたフレームワーク： 古典的なMクラス（$r=s=n/2$）から、一般化されたマイオラナ・マクファーランド（GMM）クラス（$Mr,s$、ここで$x \in \mathbb{F}_2^r, y \in \mathbb{F}_2^s$かつ$r \neq s$であり、$f(x,y) = x \cdot \phi(y) + h(y)$）への拡張を分析する。

主要な貢献と結果

• CarletのCおよびDクラス： 本論文は、ベクトル部分空間のインジケータを加えることでマイオロナ・マクファーランド形式を修正したCおよびDクラスについて詳述している。

  • クラスC： $x \cdot \pi(y) + 1_{L^\perp}(x)$ の形式を持つ関数。著者らは、置換$\pi$と部分空間$L$に関する十分条件（特に性質(C)）を要約しており、これらが関数がベントであり、かつ$M^\#$の外にあることを保証する。主要な結果には、その構成要素が非ゼロの線形構造を持たない置換が含まれる。
  • クラスDおよび$D_0$： $x \cdot \pi(y) + 1_{E_1}(x)1_{E_2}(y)$ の形式を持つ関数、およびその部分クラスである $D_0$（$x \cdot \pi(y) + \delta_0(x)$）。本論文は、$D_0 \cap M^\#$の完全な特性化を提供しており、二次的な置換の場合、所属は置換がアフィン超平面上でアフィンであるかどうかに依存することを示している。高次数の場合、関数はしばしば$M^\#$の外にある。
  • スーパークラス： 本サーベイは、インジケータを組み合わせることで形成されるスーパークラス（SC, CD, SD）を検討している。一部の組み合わせ（SCなど）が$M^\#$の外にあるベント関数を生み出す一方で、他の組み合わせ（SDなど）はベント関数自体を生成できないことを特定している。

• トレース項と$P_\tau$特性：

  • 本論文は、トレース項（例：DillonおよびKasami指数）を介して定義される単項式、二項式、および関連するベント関数をレビューしている。これら、特に特定のNiho指数を持つものは、$M^\#$の外にあることを確認している。
  • $P_\tau$特性には、多くの部分が割かれている。これは、ベント関数にトレース項の多項式結合を加えることを含み、双対関数の消滅する第2次導関数によって特徴付けられる。本論文は、$P_\tau$特性が、CまたはDクラスではカバーされない、$M^\#$の外にある無限のベント関数の族の構成を可能にすることを詳述している。

• 一般化されたマイオラナ・マクファーランド（GMM）クラス：

  • 本論文はGMMクラス（$Mr,s$）とその完成版を導入している。このクラスにおけるベント性を、「ベント集合」および「部分的に定義されたベント関数」を用いて特性化している。
  • ほとんどマイオラナ・マクファーランド（$k=1$）： 線形指数が$n/2 - 1$である関数を分析している。本論文は、「自明な」、「非適切な」、「適切な」ドメインの分割を区別しており、特定の適切な分割が$M^\#$の外にあるベント関数を生み出すことを示している。
  • $\ell$-最適関数： 最小の線形指数（$ind(f)=1$）を持つ関数について論じ、これらがマイオロナ・マクファーランド関数の「反対」であることを指摘している。性質(P1)（非消滅の第2次導関数）を持つ置換を用いた構成が、このような関数を生成する方法として強調されている。

• M-部分空間と二次的構成：

  • 本論文は、M-部分空間の深い代数的および組合せ論的分析を提供している。最大M-部分空間の数の境界を確立し、ベント関数の分類に関連付けている。
  • 二次的構成（直和、間接和、2連結および4連結）が$M^\#$の外にある関数をもたらすための必要十分条件を提示している。特に、特性外にあるベント関数の4連結は、任意のベント関数と組み合わさることで、新たに$M^\#$の外にあるベント関数を生み出すことを証明している。

意義
本論文は、よく理解されているマイオロナ・マクファーランド・クラスと、広大で大部分が未分類であるベント関数の空間との間の溝を埋める包括的なサーベイとして位置づけられている。その主な意義は以下の通りである：

1. 除外の体系化： 単なるアドホックな例を超えて、線形指数やM-部分空間に基づく構造的特性化に基づき、ベント関数がいつ$M^\#$から外れるかを決定するための統一されたフレームワークを提供すること。
2. 構成方法の拡張： 固定された次元における例の少なさを克服するために、C、D、$P_\tau$、GMMといった明示的な方法を詳述し、$M^\#$の外にある無限のベント関数の族を生成すること。
3. 代数的構造の明確化： 線形指数やM-部分空間といった概念を、ベント関数の代数的特性および一般化されたマイオロナ・マクファーランド階層との関係を理解するための基本的なツールとして導入および洗練させること。
4. 未解決問題の特定： $M^\#$におけるEA等価クラスの正確な計数、これらの理論の$p$進ベント関数への拡張、およびマクファーランド・クラスの外にある差集合の構成を含む、多数の未解決問題を挙げて締めくくること。

著者らは、$M^\#$の外にある関数を特定することにおいて重要な進展が遂げられたものの、ベント関数の総計数およびそれらの代数的構造の完全な分類は依然として未解決の課題であることを認め、控えめなトーンを維持している。本研究は、標準的なマイオロナ・マクファーランド構成では捉えられない特定の非線形特性を持つ、暗号学的に重要なブーリアン関数を設計しようとする研究者にとっての基礎的なリファレンスとして機能する。