Block Tensor Rank of Sum-Rank Metric Codes

技術要約：和ランク（Sum-Rank）距離符号におけるブロック・テンソル階数

問題提起
和ランク距離符号は、符号語を固定されたブロックに分割された行列のタプルとして表現することで、ハミング距離およびランク距離の両方を一般化したものである。ランク距離符号におけるテンソル階数不変量（符号を生成するランク1行列の最小数）は十分に研究されているが、和ランク符号のブロック構造に適応した対応する不変量は、体系的に開発されてこなかった。本論文は、サポート理論的な不変量や既存の等価性判定用のテンソル手法とは区別される、和ランク符号のための「ブロック・テンソル階数」を定義し、計算するという課題に取り組んでいる。

手法と定義
著者らは、和ランクのタプル内の単一のブロック内に完全にサポートされたランク1行列として定義されるブロック単純テンソル（block-simple tensors）の概念を導入する。和ランク符号 $C$ のブロック・テンソル階数を $btrk(C)$と表記し、これは$C$ の線形包（linear span）を含むブロック単純テンソルの最小数として定義される。

核心となる手法は以下の通りである：

1. 生成タプル（Generator Tuples）： 各符号を、線形写像を介して符号を生成する3次テンソルのタプル（各ブロックにつき1つ）に関連付ける。
2. ブロックごとの分解（Blockwise Decomposition）： 符号全体のブロック・テンソル階数が、個々のブロックへの投影のテンソル階数の総和に等しいことを証明する。これにより、大域的な問題を、標準的なランク距離符号におけるテンソル階数の問題へと還元する。
3. 座標符号（Coordinate-Code）の議論： ブロック単純基底に対する係数への写像を通じて、基本体 $\mathbb{F}_q$ 上の線リーニアブロック符号（「座標符号」）を構成する。これにより、古典的なハミング距離に基づく境界をブロック・テンソル階数の設定へと転送することを可能にする。

主要な貢献と結果

• 構造的分解定理： 本論文は、$btrk(C) = \sum_{i=1}^t trk(\pi_i(C))$ であることを確立している（ここで $\pi_i(C)$ は第 $i$ ブロックへの投影であり、$trk$ は標準的なテンソル階数を示す）。この恒等式は、ブロック・テンソル階数の計算が、各ブロックにおける独立したテンソル階数の計算に分離できることを意味している。
• 下界（Lower Bounds）： 2つの相補的な下界が導出されている：
  • 投影ベースの下界： 分解定理から直接導かれ、$btrk(C) \ge \sum N_q(k_i, d_i)$ となる（ここで $k_i$ と $d_i$ は第 $i$ 投影の次元と最小ランク距離である）。
  • 座標符号の下界： 符号のグローバルなパラメータ $(k, d)$ から導かれ、$btrk(C) \ge N_q(k, d)$ となる（ここで $N_q(k, d)$ は、次元 $k$ および最小ハミング距離 $d$ を持つ線形符号の最小長である）。
  • シンプリントンおよびグリースマーによる洗練： $N_q(k, d)$ に古典的なシンプリントン境界およびグリースマー境界を適用することで、著者らはシンプリントン座標符号境界（$btrk(C) \ge k + d - 1$）およびグリースマー座標符号境界（$btrk(C) \ge G_q(k, d)$）を導出している。
• 極限的概念：
  • BTR符号： シンプリントン座標符号境界（$btrk(C) = k + d - 1$）に達する符号。
  • ブロック・テンソル階数極限符号： より鋭い境界 $btrk(C) = N_q(k, d)$ に達する符号。
• 構成法：
  • ブロック対角リフティング（Block-Diagonal Lifting）： 古典的な線形ブロック符号（「バックボーン」）を対角写像を介して行列ブロックへと持ち上げる（lifting）一般的な手法を導入する。
  • BTRファミリー： 特定のパラメータ領域（Fat-block、Uniform MDS-backbone、Pooling regime）において、MDSバックボーン（例：リード・ソロモン符号）を用いたBTR符号の明示的な構成を提供する。
  • グリースマー最適ファミリー： グリースマー最適バックボーン（例：シンプレックス符号およびマクドナルド符号）を用いて、グリースマー座標符号境界に達する符号を構成する。これらは極限的ではあるが、$G_q(k, d) > k + d - 1$ の場合には必ずしもBTRではない。
• MSRD符号との比較： 本論文は、BTRの最適性と最大和ランク距離（MSRD）の最適性が異なるものであることを示している。具体的には、一様MDSバックボーンのリフティング領域において、符号はBTR閾値と一様MSRD次元を同時に達成することはできない。さらに、著者らは既存の構成（Chen [19] および Lao et al. [20]）に投影ギャップ基準を適用し、一部の符号はBTR閾値に近いものの、他のもの（特定のMSRD符号など）は、そのブロック投影の高いテンソル階数のために大きなギャップを示すことを明らかにしている。

意義と主張
本論文は、ブロック適応型テンソル階数の観点から和ランク符号を分析するための、最初の体系的な枠組みを提供すると主張している。その意義は以下の点にある：

1. 統合： 和ランク符号理論とテンソル分解理論、および古典的なハミング距離の境界を結びつけること。
2. 計算の削減： ブロック分解定理により、ブロック・テンソル階数の計算を既知のランク距離テンソル階数の問題へと簡略化すること。
3. 新しい最適性基準： BTRおよびブロック・テンソル階数極限符号を、MSRD符号とは異なる新しい最適符号のクラスとして導入すること。
4. 構造的洞察： 著者らは、ブロック・テンソル階数が符号の「代数的経済性（algebraic economy）」の尺度として機能すると示唆している。彼らは、この不変量が、ポスト量子暗号における構造化された符号ファミリーとランダムな符号を区別するために有用である可能性があると考えているが、具体的な暗号スキームや攻撃を提案してはいない。

結論として、論文は、リフティング構成を超えたBTR存在のパラメータ領域の分類や、構造的識別子としてのブロック・テンソル階数の潜在的な使用を含む、未解決の問題を特定している。