The Closure of LCD-to-GI Reductions via Generalized Inner Products

技術的サマリー：一般化内積による LCD から GI への帰着の閉包性

1. 問題定義

線形符号に対する**置換同値性問題（PEP）**は、2 つの与えられた線形符号が座標の置換まで同一かどうかを問うものである。この問題は、線形符号の分類と符号ベースの暗号（例えば LESS 署名方式や SPECK 方式）のセキュリティ分析の両方において基礎的である。

PEP の複雑性は**グラフ同型問題（GI）**と密接に関連している。PEP は一般的に困難であると見なされているが、Bardet ら [3] による重要な画期的成果は、線形相補的双対（LCD）符号（自明なハウル、すなわち $C \cap C^\perp = \{0\}$ を持つ符号）に対する PEP が多項式時間で GI に帰着されることを示した。この帰着は、直交射影 $\Pi_C = G^T(GG^T)^{-1}G$ を通じて LCD 符号を重み付きグラフに写すものである。

しかし、この手法はグラム行列 $GG^T$ が非特異であることを前提としており、その適用範囲を LCD 符号に限定している。非自明なハウル（$\dim(\text{Hull}(C)) \ge 1$）を持つ符号は、この特定の構成では処理できない。本論文で扱われる中心的な問いは、直交射影法をどこまで拡張できるかである。具体的には、異なる双線形形式を用いることで非自明なハウルを持つ符号に一般化できるか、また可能であるならば、そのような帰着の厳密な構造的限界は何か。

2. 手法

著者は、標準的な内積を構造行列 $M$ で表される任意の非退化対称双線形形式に一般化する。

• 一般化射影： 彼らは $M$-双対符号 $C^{\perp_M}$ と $M$-ハウル $\text{Hull}_M(C)$ を定義する。$M$-LCD 符号（$\text{Hull}_M(C) = \{0\}$）に対して、一般化された直交射影を構成する：
  $$\Pi_{C,M} = M G^T (G M G^T)^{-1} G$$
• 帰着条件： 帰着の核心は、恒等式 $\Pi_{CP, M} = P^T \Pi_{C,M} P$ に依存している。ここで $P$ は置換行列である。この恒等式は、2 つの符号が置換同値であれば、それらの射影が重み付きグラフとして同型であることを保証する。
• $M$ の特徴付け： 著者は、すべての置換 $P$ に対して $P M P^T = M$（またはそのスカラー倍）を満たす構造行列 $M$ がどのようなものかを調査する。これは、射影が置換の下で正しく振る舞うために必要である。
• 列挙とアルゴリズム： 二次形式に関する指標和（特に Weil の定理）を用いて、著者は帰着可能な符号の数を求める正確な列挙式を導出する。また、与えられた符号対を GI に帰着させる適切な $M$ を見つけようとする多項式時間アルゴリズムを構築する。

3. 主要な貢献と結果

A. 有効な構造行列の特徴付け（定理 3.5）
本論文は、直交射影法が有効な帰着（$C_1 \cong C_2 \iff \Pi_{C_1, M} \cong \Pi_{C_2, M}$）を与えるための必要十分条件は、構造行列 $M$ が以下の形式を持つことであると証明している：
$$M = aI + bJ$$
ここで、$I$ は単位行列、$J$ は全 1 行列であり、$a, b \in \mathbb{F}_q$ は非退化条件（$a \neq 0$ および $a + nb \neq 0$）を満たす。この帰着を可能にする他の非退化対称双線形形式は存在しない。これにより、直交射影アプローチの閉包性が確立される。すなわち、任意の双線形形式を選択することで手法を拡張することはできず、形式は単位行列と全 1 行列の線形結合でなければならない。

B. 帰着可能な符号の完全な特徴付け（定理 4.5）
著者は、どのような符号がこの方法で GI 帰着可能かを正確に特定する：

• 符号 $C$ がこの方法を通じて GI 帰着可能であるための必要十分条件は以下の通りである：
  1. $C$ が LCD 符号である（標準的な場合、$M=I$）、または
  2. $\dim(\text{Hull}(C)) = 1$ であり、かつ一意のハウルベクトル $x$ が $(x, \mathbf{1}) \neq 0$ を満たす（ここで $\mathbf{1}$ は全 1 ベクトル）。
• 標数 2： 標数 2 の体において、ハウル内の任意のベクトルに対して条件 $(x, \mathbf{1}) \neq 0$ は不可能である（$(x, x) = (x, \mathbf{1})^2 = 0$ が $(x, \mathbf{1}) = 0$ を意味するため）。したがって、標数 2 ではLCD 符号のみが帰着可能である。
• より高次のハウルに対する不可能性： $\dim(\text{Hull}(C)) \ge 2$ となる符号は、$M = aI + bJ$ の選択に関わらず、直交射影法を通じて帰着可能であることが証明されていない。

C. 列挙式（定理 5.3）
本論文は、奇数 $q$ に対する GI 帰着可能な $[n, k]_q$ 符号の数を数えるための正確な式を提供する。その数は以下の和である：

1. 標準的な LCD 符号の数 $L(n, k, q)$。
2. 座標和の条件を満たすハウル次元 1 の符号の数。これは、非ゼロの座標和を持つ等方的ベクトルの数と、特定の判別式を持つ商空間上の LCD 符号の質量公式を用いて導出される。

D. 帰着アルゴリズム（第 6 節）
多項式時間アルゴリズムが提示される：

1. ハウル次元をチェックする。$\ge 2$ であれば、「GI 帰着不可」と出力する。
2. LCD 符号であれば、$M=I$ を使用する。
3. ハウル次元が 1 の場合、両方の符号を $M$-LCD にするようなスカラー $b$ を探索し、$M = I + bJ$ とする。
4. 一般化された射影を構成し、得られたグラフ同型問題を解く。

4. 意義と主張

本論文は、直交射影法の能力に関する完全な特徴付けを提供すると主張している。

• 閉包性： Bardet らの帰着を、この特定の手法を用いて大きなハウル（$\ge 2$）を持つ符号に拡張する可能性を明確に否定する。この手法は本質的にハウル次元が最大 1 の符号（標数 2 では LCD 符号のみ）に限定されることを証明している。
• 構造的限界： 帰着が機能するために必要な特定の代数構造（$M = aI + bJ$）を特定し、他の対称双線形形式はこの写像を可能にできないことを示している。
• 暗号への示唆： 結果は、符号ベースの暗号方式（SPECK など）のパラメータ選択における基準を提供する。これにより、ハウル次元を $\ge 2$ となるように設計し、この特定の GI 帰着攻撃ベクトルの及ばない範囲に置くことが可能になる。

著者は、$\dim(\text{Hull}(C)) \ge 2$ の符号に対する PEP を GI に写す他の帰着戦略（直交射影に基づかないもの）が存在するか、あるいはそのような帰着が証明不可能であるかという未解決の問題を提起して結論としている。