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$ 上的 Hermitian 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 嵌入的生成矩阵。如果 $G$ 是一个由生成壳的部分 $G(\text{Hull}(C))$ 和剩余部分 $A$ 组成的码 $C$ 的生成矩阵，那么一个最短 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 码。通过计算这些现有码的壳维度，并根据推导出的结构附加必要的列，他们生成了新的 LCD 码。

主要贡献与结果
本文提供了理论界限和具体的构造方案：

• 理论结果：

  • 证明了具有壳维度 $\ell$ 的 $[n, k]$ 码的最短 LCD 嵌入长度为 $n + \ell$。
  • 刻画了所有可能的此类最短嵌入的生成矩阵形式，表明它们等价于在壳生成的行中附加一个可逆矩阵。
  • 证明了码 $C$ 的最短 LCD 嵌入的长度与其壳 $\text{Hull}(C)$ 的最短 LCD 嵌入长度相同。

• 新码构造：
  通过对现有线性码使用最短 LCD 嵌入法，作者构造了若干个具有改进最小距离的新型 LCD 码：

  • 三进制 LCD 码：
    • $[23, 4, 14]$：将已知最小距离从 13 提高到 14。
    • $[23, 5, 12]$：将已知最小距离从 11 提高到 12。
    • $[24, 6, 12]$：将已知最小距离从 11 提高到 12。
    • $[25, 5, 14]$：将已知最小距离从 13 提高到 14。
  • 四进制 Hermitian LCD 码：
    • $[21, 10, 8]$：将已知最小距离从 7 提高到 8。

作者指出，对于新参数 $[23, 4, 14]$ 和 $[23, 5, 12]$，他们分别发现了 226 个和 38 个不等价的码。这些码是距离最优的，且不等价于目前 BKLC（最佳已知线性码）数据库中的码。

意义
本文声称，最短 LCD 嵌入法是寻找各种域上距离最优 LCD 码的有用工具。通过确定精确所需的列数并刻画其结构，该方法提供了一条将已知线性码转换为 LCD 码时提高其最小距离的建设性路径。结果表明，该方法成功地为特定的三进制和四进制参数生成了最小距离比原先已知码高 1 的新码。

局限性与未来方向
作者承认其方法存在一个局限性：由于所附加的可逆矩阵和任意矩阵的搜索空间过于庞大，很难保证能找到能产生给定码之绝对最大最小距离的具体嵌入。他们建议，未来的研究应侧重于开发更具策略性的方法来选择附加矩阵，以最大化生成的最小距离，或者确定是否可以在等价意义下进一步限制附加矩阵，以缩小搜索空间。