技術要約：コード歪曲問題（Code Distortion Problem）

問題の定義

本研究は、線形符号等価問題（Linear Code Equivalence Problem, LCE）の一般化である**コード歪曲問題（Code Distortion Problem, CDP）**を導入し、その研究を行うものである。LCEが、2つの線形誤り訂正符号 $C_1, C_2 \subseteq \mathbb{F}_q^n$ が線形等長写像（座標置換とスケーリングを含む距離保存写像）によって関連付けられているかどうかを問うものであるのに対し、CDPは、2つの符号が完全に等価ではない場合に、それらの「類似性」をどのように定量化するかを追求するものである。

形式的には、2つの $[n, k]_q$ 符号 $C_1, C_2$ に対して、$T(C_1) = C_2$ となる線形写像 $T$ の歪曲は次のように定義される：
$$D_T(C_1, C_2) := \left( \max_{x \in C_1 \setminus \{0\}} \frac{\|Tx\|_0}{\|x\|_0} \right) \Bigg/ \left( \min_{x \in C_1 \setminus \{0\}} \frac{\|Tx\|_0}{\|x\|_0} \right)$$
ここで $\|\cdot\|_0$ はハミング重みを表す。コード歪曲 $D(C_1, C_2)$ は、そのような線形写像における最小の歪曲である。決定問題である GapCDP は、与えられた閾値 $D$ と近似係数 $\gamma$ に対して、$D(C_1, C_2) \leq D$ であるか、あるいは $D(C_1, C_2) > \gamma D$ であるかを問うものである。

この問題は、LCEの暗号学的重要性（例：LESS暗号システム）および、厳密には等価ではない符号間の構造的な距離を理解したいという動機に基づいている。

手法と技術

著者らは、Bennett, Dadush, および Stephens-Davidowitz (2016) による**格子歪曲問題（Lattice Distortion Problem, LDP）**で使用された手法と同様の手法を用いつつ、符号理論に特有のいくつかの新しい概念を導入している。

1. 符号の逐次最小基底（Successive Minima Bases for Codes）： 格子理論から適応されたものであり、$i$ 番目の逐次最小値 $\lambda_i(C)$ は、重みが最大 $r$ である $i$ 個の線形独立なベクトルを $C$ が含むような最小の重み $r$ である。逐次最小基底とは、$i$ 番目の列の重みが正確に $\lambda_i(C)$ となる生成行列である。著者らは、このような基底は常に存在し、$O^*(q^k)$ 時間で計算可能であることを証明している。
2. 行列 $0 \to 0$ ノルム： 本論文では、「ノルム」 $\|T\|_{0 \to 0} = \max_{x \neq 0} \|Tx\|_0 / \|x\|_0$ を分析している。無制限のノルムは効率的に計算可能であるが、制限されたノルム（部分空間または符号上で最大化されるもの）は、近似することが coNP困難であることが示されている。
3. 簡約（Reductions）：
   • 困難性： 著者らは、格子の最短ベクトル問題（SVP）から最近接ベクトル問題（CVP）への Goldreich-Micciancio-Safra-Seifert (GMSS) による簡約を適応させ、符号における最小距離問題（GapMDP）から最近傍符号器問題（GapNCP）への同様の簡約を作成した。これはさらに GapCDP へと簡約される。
   • 近似： コアとなるアルゴリズム的アプローチは、両方の入力符号の逐次最小基底を計算し、一方の基底ベクトルを他方へ写像することである。

主要な貢献と結果

1. 複雑性と近似の困難性

• NP困難性： 本論文は、定数歪曲閾値 $D > 1$ に対して、決定問題である GapCDP が任意の定数因子 $\gamma$ で近似することさえ NP困難 であることを証明している。これは、$D=1$（LCE）の場合が coAM に属し、NP困難とは考えられていないこととは対照的である。
• 複雑性クラス： GapCDP は $\Sigma_2^P$（多項式階層の第2レベル）に属することが示されている。著者らは、証拠（低歪曲写像）を検証するには制限された行列 $0 \to 0$ ノルムを計算する必要があり、それが coNP困難であるため、問題が NP に属するかどうかは即座には明らかではないと述べている。
• 行列ノルムの困難性： 副産物として、本論文は、部分空間に制限された行列 $0 \to 0$ ノルムを近似することが coNP完全 であることを確立している。

2. 近似アルゴリズム

著者らは、逐次最小基底に基づく単一指数時間の近似アルゴリズムを提供している。

• 一般ケース： 任意の $[n, k]_q$ 符号に対して、$O^*(q^k)$ 時間で動作し、$k^2$ 近似を実現するアルゴリズムが存在する。このアルゴリズムは、逐次最小基底 $G_1, G_2$ を計算し、$G_1 \to G_2$ を写像する。
• 特殊ケース（バイナリ、一様最小値）： すべての逐次最小値が等しい（$\lambda_1 = \dots = \lambda_k$）バイナリ符号の場合、近似係数は $\left(\frac{2k+1}{3}\right)^2$ に改善される。この解析は、同一の符号の2つの生成行列間の歪曲がこの境界を達成するという構成的な例によって、タイト（tight） であることが示されている。

3. 厳密アルゴリズム

実行時間が $O^*(q^{k(k+1)})$ となる総当たり的な厳密アルゴリズムが提示されており、これは対象となる符号のすべての生成行列を列挙することに相当する。著者らは、これを単一指数時間の厳密アルゴリズムへと改善することは依然として未解決の課題であると述べている。

意義と主張

本論文は、コード歪曲問題の基本的な計算論的景観を確立することを主張している。

• 一般化： よく研究されている LCE を、コードの類似性の定量的指標へと見事に一般化し、計量埋め込み（metric embeddings）と格子理論の概念を橋渡ししている。
• 困難性の障壁： 完全な等価性からのわずかな逸脱（$D > 1$）が、問題を計算量的に手に負えないもの（近似することさえ NP困難）にすることを実証しており、これは「ほぼ等価な」符号を見つけることが困難であることを示唆している。
• アルゴリズムの限界： CDP に対する最初の非自明な近似アルゴリズムを提供しており、厳密な解は高コストであるが、逐次最小基底を用いることで、単一指数時間で良好な近似が可能であることを示している。
• 理論的ツール： 符号の逐次最小基底の導入と、制限された $0 \to 0$ ノルムの分析は、それ自体が独立した関心事であり、符号理論や複雑性理論の将来の研究において有用である可能性がある。

著者らは、CDP と格子歪曲問題（LDP）の関係、および LESS 暗号システムにおける LCE への依存と同様に、近似された CDP の困難性に依拠した暗号学的安全性の可能性についても、さらなる調査が必要であると述べて締めくくっている。