🔢 数学

Constructing Complete Permutations via the D-Class of Locally Crooked Permutations

本論文は、局所的な共役変換を通じて完全置換を特徴付け、構成するために $\mathbb{F}_{2^{n+1}}$ 上の $D$ 級置換を導入し、それらの代数的性質、暗号学的境界、および CCZ 不等価性を確立するとともに、新たな $\delta=4$ の完全置換を正常に列挙するアルゴリズムを提示する。

原著者： Li Shuai

公開日 2026-10-16

📖 1 分で読めます🧠 じっくり読む

CC BY 4.0

原著者： Li Shuai

原論文は CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

現代のデジタルセキュリティの隠れた構造の中には、「完全置換（complete permutations）」として知られる数学的対象のクラスが存在する。これらは単なる数字の無作為なシャッフルではない。それらは、ある要素を新しい位置に移動させる行為と、その要素を「元の位置と新しい位置の和」の位置に移動させる行為の両方が、完璧で重複のない秩序をもたらすという、高度に構造化された並べ替えである。この二重の要件は、データの意味を隠すためにデータを撹乱する暗号システムの主要構成要素である、代入箱（Sボックス）の設計において極めて重要である。もしこれらのコンポーネントが予測可能すぎれば暗号は破られ、もし混沌としすぎていれば効率が悪くなる。暗号学者の長年の課題は、洗練された攻撃に耐えうるほど複雑でありながら、迅速に実装できるほど構造化されているという、スイートスポットを見つけることであった。

寧夏大学の李帥による最近の研究は、幾何学的な対称性の観点から、これらの置換の特定のファミリーを探索することで、この課題に取り組んでいる。この研究は、「局所的な曲がり具合（local crookedness）」と呼ばれる特性に焦点を当てている。これは、入力が特定の量だけシフトされたときに、置換がどのように振る舞うかを表している。著者は、出力の変化パターンによって定義される特定の関数の新しいカテゴリーを導入している。これらの関数を、データの特定の部分をシフト、回転、または入れ替えることによって変換できる、より大きな群の要素として扱うことで、研究は可能性の景観（ランドスケープ）を描き出した。目的は、この景観内を移動することで、差分解読法（攻撃者が秘密鍵を推測するために、入力の小さな変化が出力にどのように影響するかを研究する方法）に対してより優れた保護を提供する、新しい、より優れた置換を生成できるかどうかを確認することであった。

この研究の核心は、既知の、性質の良い置換から始まり、一連の精密な代数演算を適用して新しい置換を作成するという構築チェーンにある。著者は、これらの置換が有効であり続けるために従うべき特定の規則の集合、すなわち「Dクラス」を定義している。この集合の中で、研究者は「リフトされた（lifted）」置換（より小さな空間からより大きな空間へと拡張されたもの）のコレクションが、独特の剛性（rigidity）を持つことを証明している。もし、単純なシフトや線形回転のような単一の操作のみを用いて一つの置換を変更しようとすれば、その結果は通常、有効な完全置換としての性質を維持できなくなる。しかし、本研究は、二つの異なる操作を特定の順序で組み合わせることで、この剛性を打破できることを示している。この組み合わせにより、研究者は、セキュリティに必要な本質的な特性を失うことなく、一つの有効な置換から別の有効な置換へと、可能性の空間を航行することが可能になる。

この理論的枠組みを実用的にするために、論文では二つの異なるアルゴリズムを開発している。第一は、すべてのステップにおいて二重の順序要件が満たされていることを確認しながら、ゼロから完全置換を構築するバックトラッキング探索である。第二は、既存の置換から始まり、前述の組み合わせ操作を適用することでそれを改善しようとする、貪欲な局所探索（greedy local search）である。この第二のアルゴリズムは、高い頂点を目指す登山家のように機能する。それは様々な小さな修正をテストするが、その変更が置換の暗号学的品質を厳格に向上させる場合にのみ、その変更を受け入れる。品質は、差分一様性（出力パターンの最悪の頻度を数えるもの）と、非線形性（関数が単純な線形方程式からどの程度離れているかを測るもの）という二つの主要な指標によって測定される。差分一様性は低く、非線形性は高いことが、一般にセキュリティにとって望ましい。

研究者たちは、32のサイズ（5ビットシステムに対応）の特定の数学的空間に対して、これらの手法をテストした。弱さが知られている単純な線形置換から開始し、貪欲探索アルゴリズムを100回実行した。実験の結果、開始時の値である32から大幅に改善された、差分一様性4の置換がいくつか得られた。また、100個のランダムに生成された置換から開始し、同じ探索プロセスを適用した。ここでも、アルゴリズムは一貫して差分一様性4の置換を見出した。結果は単に優れた数値を見つけることだけではなく、新しい置換は互いに、また開始点とも異なる独自の「スペクトル（出力頻度のパターン）」を有していた。これは、この手法が単に同じオブジェクトの変種を生み出しているのではなく、真に新しい、明確に区別される安全な置換のクラスを発見していることを証明している。

最も顕著な発見の一つは、これらの新しい置換と、APN（Almost Perfect Nonlinear）関数として知られる有名な関数のクラスとの関係に関するものである。歴史的に、安全な置換の構築の多くは、これらのAPN関数から開始することに依存してきた。しかし、本研究では、この新しい局所共役法（local-conjugation method）によって生成された置換が、優れた差分一様性4を持つ一方で、古典的なAPNアプローチから導出されたものとはCCZ不等価であることを発見した。実際、よく知られたAPN関数に基づく参照用置換は、この特定のテストにおいて、差分一様性8という、より低い性能を示した。これは、この新しい手法が数学的景観の異なる領域を探索しており、標準的な構築技術では到達不可能であった高品質な置換を掘り起こしていることを示唆している。

論文は、実験的証拠に基づいたある推測を提示して締めくくっている。それは、これらリフトされた置換の空間全体が連結しているというものである。言い換えれば、これらの特定の局所的な修正に従うことで、このファミリー内の任意の有効な置換に、他の任意の置換から到達することが可能であるように見える。この連結性は数学的に証明されていないが、探索アルゴリズムが多様な開始点から一貫して高品質な解を見出したという事実は、この考えに対する強力な予備的根拠を提供している。また、本研究は、この特定の置換ファミリーの中に、今回見つかったものよりもさらに強力な、APNとして知られる理論的限界のセキュリティに達する関数が含まれているかどうかという問いを、未解決のまま残している。現時点では、本研究は安全な置換を生成するための堅牢な新しいツールキットを提供しており、これらの数学的対象の局所的な対称性を理解することで、デジタル世界のためのより良い防御を構築できることを示している。

テクニカルサマリー：局所的に曲がった置換のDクラスによる完全置換の構成

問題提起

本論文は、有限体 $\mathbb{F}_{2^n}$ 上の**完全置換（Complete Permutations: CPs）**の構成について扱っている。置換 $f$ がCPであるとは、 $f$ と写像 $x \mapsto f(x) + x$ の両方が置換であることを指す。CPsは、ライ・マシー（Lai–Massey）フレームワークにおけるSボックスの構成要素や、直交ラテン方格の生成において極めて重要である。

CPsは、Shuai–Liの対応関係を通じて $\mathbb{F}_{2^{n+1}}$ 上の**局所的に曲がった置換（Locally Crooked Permutations: LCPs）**と結びついているが、従来の手法は「曲がった関数 $\to$ LCP $\to$ CP」という経路に依存していた。このアプローチは制約が多く、LCPのクラス自体の中で新しいLCPを自由に移動したり生成したりすることを許容していなかった。本論文は、LCPのクラス内部で内部群作用を用いて新しいCPsを生成することにより、この問題を克服することを目指している。

手法

1. Dクラスと不変性

著者は、固定された方向 $q_1 = 2^n$ における微分値の像が、固定された超平面 $H = \{x : x_n = 0\}$ の補集合に等しいような $\mathbb{F}_{2^{n+1}}$ 上の置換 $f$ の集合として定義されるDクラスを導入する。
$D = \{f \in S_q : \text{Im } \Delta_{q_1}f = K\}$
ここで $K = \mathbb{F}_{2^{n+1}} \setminus H$ である。

本論文は、 $D$ が以下の3つの特定の群作用の下で閉じていることを証明している。

左平行移動: 任意の $a \in \mathbb{F}_q$ に対する $t_a \circ f$ 。
左乗算: $H$ を保存する一般線形群 $GL_H$ 内の任意の $g \circ f$ 。
右乗算: $H$ と $K$ を入れ替える対合の交換子 $C$ 内の任意の $f \circ h$ 。

さらに、このクラスは、平行移動と共役な対合によって生成される特定の二面体群の軌道の和集合である場合に限り、特定の局所平行移動 $t_{a,X}$ （部分集合 $X$ に制限された平行移動）の下でも閉じている。

2. 硬直性と構成の連鎖

著者は、 $K$ の補集合上で恒等写像として作用する $D$ 内の置換のサブクラス $D^\uparrow$ （リフトされたCPサブクラス）を定義する。

硬直性（Rigidity）: 本論文は、 $D^\uparrow$ が上記の閉包特性（平行移動、線形乗算、または交換子乗算）のいずれか単一の操作に対して「硬直」していることを証明している。単一の操作では、恒等写像でない限り、リフトされたCPを別のリフトされたCPに写すことはできない。
構成の連鎖: 新しいCPsを生成するために、著者は一連の操作の積を含む連鎖を構築する。
$CP \xrightarrow{\text{lift}} LCP \xrightarrow{\text{local translation}} LCP' \xrightarrow{\text{centralizer correction}} LCP'' \xrightarrow{\text{restriction}} \text{New } CP$
この連鎖は、局所平行移動によって導入される欠陥を「修復」し、結果が $D^\uparrow$ に留まることを保証するために、局所化された交換子要素（ $g_{a,X_1}$ および $g_{a,X_2}$ ）を利用している。

3. 局所共役

この構成は、基本体 $\mathbb{F}_{2^n}$ 上で定義される2つの特定の局所共役 $f_1$ および $f_2$ をもたらす。

$f_1$ : 二面体群の下で不変な部分集合 $X_1 \subset H$ 上での $f$ の修正。
$f_2$ : 巡回群の下で不変な部分集合 $X_2$ 上での $f$ の逆写像を用いた修正。
本論文は、これらの修正された写像がCPであり続けるための必要十分条件を提示している。

4. アルゴリズム

理論を実装するために2つのアルゴリズムが提示されている。

ランダム・バックトラッキング探索: $f(x)$ と $f(x)+x$ に対する制約を維持しながら、ゼロからランダムなCPsを生成する。
貪欲な局所探索（Greedy Local Search）: シードとなるCPに局所共役（ $f_1, f_2$ ）を反復的に適用する。これは、完全な微分スペクトル（DDT）およびウォルシュ・スペクトルに基づく品質関数を厳密に改善する場合にのみ、移動を受け入れる。

主要な結果

理論的貢献

不変性の証明: Dクラスが指定された群作用および局所平行移動の下で不変であることを確立した。
硬直性定理: リフトされたCPサブクラス $D^\uparrow$ は単一の操作では生成できないことを証明し、複合的な構成連鎖が必要であることを示した。
CCZ不等価性の判定基準: 新しく構成されたCPsがシードとCCZ不等価であるかどうかを判断するための基準を導出した。これは、微分分布表（DDT）または絶対ウォルシュ係数のマルチセットが変化するかどうかをチェックすることに基づいている。
暗号学的境界: 局所的な修正下での微分一様性（ $\delta$ ）、非線形性（$nl $）、および代数次数（$ \deg $）の境界を導出した。具体的には、$ \delta $は修正された部分集合のサイズ$ m $に対して最大$ 2m$ 変化する。

実験的知見

$H \cong \mathbb{F}_{2^5}$ （32要素）を用いて実験が行われた。

$\delta=4$ のCP生成: 線形シード（ $\delta=32$ ）およびランダムシードから開始して、貪欲探索は $\delta=4$ の複数の完全置換の生成に成功した。
異なるスペクトル: 生成されたCPsは、互いに、また参照用のDillonベースのCP（ $\delta=8$ ）に対して異なる微分スペクトルを示した。
CCZ不等価性: 異なる微分スペクトルは、この構成が単なるシードのアフィン変種ではなく、新しいCCZ不等価クラスを生成していることを裏付けている。
連結性の証拠: 異なるランダムシードから同様のインジケーター分布に繰り返し収束することは、 $D^\uparrow$ の集合が局所共役移動の下で連結である可能性を示唆する予備的な証拠を提供している。

意義と主張

本論文は、LCPクラスの内部構造を利用することで、新しい完全置換を生成するための体系的な代数的枠組みを提供すると主張している。

曲がった関数を超えて: 曲がった関数から始めることに依存していた従来の手法とは異なり、このアプローチはLCP空間自体を探索してCPを見つけることを可能にする。
暗号学的有用性: この手法は、Sボックスとして望ましい特性である低い微分一様性（ $\delta=4$ ）を持つCPsを生成することに成功しており、これは標準的な曲がった関数の対応関係からは構築が困難であった。
構造的洞察: $D^\uparrow$ の「硬直性」と、局所平行移動を「修復」する際の交換子の特定の役割の特定は、LCPとCPの関係に関するより深い理論的理解を提供する。
未解決問題: 著者は、 $D^\uparrow$ の連結性とこのクラス内におけるAPN関数の存在を未解決問題として控えめに位置づけており、実験結果は連結性を支持しているものの、形式的な証明が必要であることを示唆している。また、結果はAPN置換への潜在的な関連性を示唆しているものの、本研究においてAPN置換が明示的に確立されたわけではないことも述べている。