Function-Based Minimal Linear Codes over Galois Rings $\mathrm{GR}(p^{n}, \ell)$: Minimality Criteria and Infinite Constructions

这是一份关于论文《Function-Based Minimal Linear Codes over Galois Rings GR(pn, ℓ): Minimality Criteria and Infinite Constructions》（基于函数的伽罗瓦环 GR(pn, ℓ) 上的极小线性码：极小性判据与无限构造）的详细技术总结。

1. 研究背景与问题 (Problem)

背景：
极小线性码（Minimal Linear Codes）在秘密共享方案、多方计算（MPC）和可验证秘密共享（VSS）等密码学应用中具有核心地位。极小码的码字对应于秘密共享方案中的最小授权子集。近年来，研究重心从有限域扩展到了有限环，特别是伽罗瓦环（Galois Rings, GR），因为环结构（存在零因子和更丰富的模结构）为码的设计提供了更大的灵活性，并在后量子密码学和去中心化系统中展现出潜力。

核心问题：
尽管 Wu 等人（2022）已在有限域上建立了基于函数的极小线性码构造框架，但将其推广到伽罗环 $GR(p^n, \ell)$ 面临巨大的代数挑战：

1. 零因子的存在： 环中存在非零的零因子，导致向量空间理论中的许多性质（如非零向量自动无挠）不再成立。
2. 模结构的复杂性： 伽罗环是链环（Chain Ring），其理想结构呈链状，且存在挠（Torsion）现象，使得正交模的结构比有限域情况复杂得多。
3. 缺乏系统性判据： 目前缺乏针对伽罗环上基于函数的线性码的完整极小性充要条件，以及构造无限族极小码的系统方法。

目标：
本文旨在建立伽罗环 $GR(p^n, \ell)$ 上极小线性码的完整结构特征，推导基于函数的极小性判据，并构造出新的无限族极小线性码。

---

2. 方法论 (Methodology)

本文采用代数编码理论与模论相结合的方法，主要步骤如下：

1. 代数结构分析：

   • 利用伽罗环 $GR(p^n, \ell)$ 的 $p$-进分解和泰希米勒（Teichmüller）系统，分析单位元、零因子及理想的链状结构。
   • 利用伽罗环作为**弗罗贝尼乌斯环（Frobenius Ring）**的性质，特别是双重正交性 $(C^\perp)^\perp = C$，将支持集包含问题转化为正交性问题。

2. 根词（Root Words）分类与简化：

   • 引入“根词”概念：向量 $v$ 是根词当且仅当其模 $p$ 约化后非零（即至少有一个分量是单位元）。
   • 关键定理（Theorem 17）： 证明了对于维度 $m \ge 2$ 的线性码，整个码的极小性完全由其根词的极小性决定。非根词（即被 $p$ 整除的向量）产生的挠层不会引入新的极小性障碍。这一发现将复杂的环上问题简化为对根词及其正交模的分析。

3. 基于函数的构造框架：

   • 采用 Wu 等人的生成矩阵框架，定义码 $C_f$ 由函数 $f: GR(p^n, \ell)^m \to GR(p^n, \ell)$ 的取值生成。
   • 将码字分为五种类型（基于系数是单位元还是零因子，以及向量是否为根词），并针对每种类型推导极小性的充要条件。

4. 同步条件（Synchronization Conditions）：

   • 利用 McCoy 秩（McCoy Rank）和模约化技术，将环上的线性无关性问题转化为有限域上的秩问题。
   • 建立函数 $f$ 与线性形式 $w \cdot x$ 之间的“同步条件”：
     • 对于单位元情况：$f(\beta_i) = w \cdot \beta_i$
     • 对于零因子情况（$d = p^r u$）：$p^r f(\beta_i) = w \cdot \beta_i$
   • 通过构造特定的基（如全支撑基、低汉明重量基），验证这些条件是否满足。

---

3. 主要贡献与结果 (Key Contributions & Results)

A. 理论判据的完善

1. 极小性充要条件： 建立了 $GR(p^n, \ell)$ 上 $m$ 维线性码极小性的充要条件（Proposition 14, Theorem 17）。证明了当 $m \ge 2$ 时，只需验证所有根词生成的码字是否为极小码字。
2. 长度下界： 推导了 $m$ 维极小线性码长度的显式下界。
   • 当 $m \ge 3$ 时：$k > (m-1)q^n + q^{n-m}$
   • 当 $m = 2$ 时：给出了针对不同 $n$ 值的精确下界，并证明了 $k(2; GR(p^n, \ell)) = q^n + q^{n-1}$，推广了 $\mathbb{Z}_{p^n}$ 上的已知结果。

B. 基于函数的构造方法

提出了两种基于函数 $f$ 的极小码构造准则：

1. 定理 40（通用构造）： 给出了函数 $f$ 需满足的四个条件（涉及汉明重量、单位元分量、零因子分量等），使得生成的码 $C_f$ 是极小的。
   • 核心思想：利用全支撑基（所有分量为单位元）和低重量基（汉明重量 $\le 2$）来分别处理不同类型的根词。
2. 定理 43（替代构造）： 提供了另一组基于函数行为（如 $f(x)=0$ 或 $f(x)=p^r$）的判据，进一步简化了构造过程。
3. 多项式构造（定理 45）： 将上述理论应用于多元多项式。证明了若 $f(x)$ 是满足特定支撑集不相交且指数条件的单项式之和，则生成的码是极小的。

C. 无限族构造

• 利用上述判据，成功构造了 $GR(p^n, \ell)$ 上的无限族极小线性码。
• 这些构造不仅推广了 Wu 等人（2022）在有限域上的结果，还揭示了环结构下极小码的新特性（如零因子对同步条件的修正）。

D. 参数分析

• 确定了构造出的码的参数 $[k, m+1]$，其中长度 $k$ 取决于定义域的大小和函数的性质。
• 证明了当 $n=1$ 时（即退化为有限域），结果与经典文献完全一致，验证了理论的正确性。

---

4. 技术细节与关键发现

• 根词与正交模： 论文详细分析了根词 $v$ 的正交模 $v^\perp$ 是自由模（秩为 $m-1$），而非根词的正交模包含挠子模。这种结构差异是分类讨论的基础。
• 零因子的处理： 在零因子情形下，极小性条件从简单的 $f(\beta) = w \cdot \beta$ 修正为 $p^r f(\beta) = w \cdot \beta$。这一修正反映了伽罗环中 $p$-进估值（valuation）对线性关系的约束。
• McCoy 秩的应用： 利用 McCoy 秩将环上的线性无关性判定转化为模 $p$ 约化后的有限域上的秩判定，极大地简化了证明过程。
• 基的构造技巧： 论文构造了多种特殊基（如 Lemma 32 中的全单位元基，Lemma 34 中的低重量基），这些基在验证同步条件时起到了关键作用。

---

5. 意义与展望 (Significance & Future Work)

学术意义：

1. 理论统一： 本文建立了一个统一的框架，将极小码理论、弗罗贝尼乌斯环上的模对偶性以及基于函数的码构造联系起来。
2. 填补空白： 首次系统性地解决了伽罗环上基于函数的极小码构造问题，克服了零因子带来的代数障碍。
3. 推广性： 结果不仅适用于伽罗环，其关于根词简化的思想也为研究其他有限弗罗贝尼环上的极小码提供了思路。

应用价值：

• 为秘密共享方案提供了更多样化的底层码结构选择，特别是在需要利用环结构（如后量子密码中的格基密码）的场景下。
• 构造出的无限族极小码具有明确的参数，便于工程实现和性能评估。

未来方向（Open Problems）：

• 重量分布： 确定构造出的极小码的完整重量分布（Weight Distribution）。
• 少重量码： 寻找能生成少重量极小码的函数条件，这对认证方案尤为重要。
• 一般弗罗贝尼环： 将结果推广到更一般的有限弗罗贝尼环。
• 密码学应用： 深入探讨这些码在基于环的秘密共享和认证码中的具体应用。
• 渐近性能： 研究当维度 $m$ 或环参数 $n$ 增大时，这些码的渐近性能。

总结：
该论文通过深刻的代数分析，成功地将有限域上的极小码构造理论推广到了伽罗环这一更复杂的代数结构上，不仅提供了严格的数学判据，还给出了具体的构造方法，为环上编码理论的发展做出了重要贡献。