Shortest LCD embeddings of binary, ternary and quaternary linear codes

問題設定
線形補完双対符号（LCD符号）は、サイドチャネル攻撃やフォールト注入攻撃に対する耐性の観点から、符号理論および暗号理論において重要な研究分野である。$\mathbb{F}_q$ ($q \ge 4$) 上のすべての線形符号がLCD符号と等価であることは既知であり、$\mathbb{F}_{q^2}$ についても同様の結果が存在するが、$\mathbb{F}_2$、$\mathbb{F}_3$、および $\mathbb{F}_4$ 上のエルミート型LCD符号における最小距離の境界については、多くの長さと次元において未解明のままである。符号理論における中心的な課題は、与えられた長さと次元に対して最大の最小距離を決定することである。本論文は、任意の線形符号をLCD符号へと埋め込むという特定の問題に取り組み、そのような埋め込みを最短で行うこと（最小限の長さ増加）を目指し、この手法を用いて新たな距離最適LCD符号を構築することを目的としている。

手法
著者らは、生成行列に最小限の列を追加することによって、与えられた線形符号 $C$ をLCD符号 $\tilde{C}$ へ埋め込むための系統的なアプローチを導入している。その手法は以下の通りである：

1. 理論的基礎： 本論文は、$[n, k]$ 符号 $C$ をLCD符号へと埋め込むために必要な最小の列数 ($m$) が、正確に $C$ のハル（hull）の次元 $\ell$ （ここで $\text{Hull}(C) = C \cap C^\perp$ である）に等しいことを確立している。したがって、最短のLCD埋め込みの長さは $n + \ell$ である。
2. 構造的特徴付け： 著者らは、最短LCD埋め込みの生成行列を特徴付けている。もし $C$ の生成行列 $G$ が、ハルを生成する部分 $G(\text{Hull}(C))$ と残りの部分 $A$ に分解できるならば、最短LCD埋め込みは以下の形式の行列によって生成される：
   $$\tilde{G} = \begin{bmatrix} G(\text{Hull}(C)) & D \\ A & C \end{bmatrix}$$
   ここで、$D$ は $\ell \times \ell$ の可逆行列であり、$C$ は任意の $(k-\ell) \times \ell$ 行列である。本論文は、ハルに対応する行に可逆行列を付加し、残りの行に任意の行列を付加することが、常に最短LCD埋め込みを与えることを証明している。
3. 構築戦略： 著者らは、この埋め込み手法を、自身はLCDではない既知の距離最適線形符号（具体的には、3元および4元符号）に適用している。これらの既存の符号のハル次元を計算し、導出された構造に従って必要な列を付加することで、新たなLCD符号を生成している。

主要な貢献と結果
本論文は、理論的な境界と具体的な構築の両方を提供している：

• 理論的結果：

  • ハル次元 $\ell$ を持つ $[n, k]$ 符号の最短LCD埋め込みの長さは $n + \ell$ であることを証明した。
  • これらの最短埋め込みの可能なすべての生成行列の形式を特徴付け、それらがハルを生成する行に可逆行列を付加することと等価であることを示した。
  • 符号 $C$ の最短LCD埋め込みの長さは、そのハル $\text{Hull}(C)$ の長さと同一であることを示した。

• 新しい符号の構築：
  既存の線形符号に対して最短LCD埋め込み法を適用することにより、著者らは既知の最小距離を改善するいくつかの新しいLCD符号を構築した：

  • 3元LCD符号：
    • $[23, 4, 14]$：既知の最小距離を13から14へ改善。
    • $[23, 5, 12]$：既知の最小距離を11から12へ改善。
    • $[24, 6, 12]$：既知の最小距離を11から12へ改善。
    • $[25, 5, 14]$：既知の最小距離を13から14へ改善。
  • 4元エルミート型LCD符号：
    • $[21, 10, 8]$：既知の最小距離を7から8へ改善。

著者らは、新しいパラメータ $[23, 4, 14]$ および $[23, 5, 12]$ について、それぞれ226個および38個の不等価な符号が見つかったと述べている。これらの符号は距離最適であり、BKLC（Best Known Linear Codes）データベースにあるものとは不等価である。

意義
本論文は、最短LCD埋め込み法が、様々な体の上で距離最適LCD符号を見つけるための有用なツールであることを主張している。必要な列数とそれらの構造を正確に決定することで、この手法は、既存の線形符号をLCD符号に変換する際に最小距離を向上させるための構成的な経路を提供する。その結果は、このアプローチが、特定の3元および4元のパラメータに対して、既知の符号よりも最小距離が1大きい新しい符号を正常に生成できることを示している。

限界と今後の方向性
著者らは、自身の手法における限界を認めている。付加される可逆行列および任意の行列の探索空間が過度に大きいため、与えられた符号に対して絶対的な最大最小距離をもたらす特定の埋め込みを見つけ出すことを保証するのは困難である。彼らは、将来の研究において、付加される行列をより戦略的に選択して結果としての最小距離を最大化するか、あるいは探索空間を縮小するために、付加される行列が等価性の範囲内でさらに制限可能かどうかを判断することに焦点を当てるべきであると示唆している。