The Star Product of Uniformly Random Codes

技术摘要：均匀随机码的星积（Star Product）

问题陈述
本文研究了两个独立的、在有限域 $\mathbb{F}_q$ 上的均匀随机线性码 $C_1$ 和 $C_2$ 的星积（也称为 Schur 积或 Hadamard 积）的期望维度。这些码具有预设的维度 $k_1, k_2$ 和长度 $n$。虽然星积是编码理论中的一项基本运算，在量子纠错、隐私信息检索（PIR）以及安全分布式矩阵乘法（SDMM）中有着广泛应用，但两个随机码的星积维度并非显而易见。以往的工作（如 [19]）通过分析秩为 1 的矩阵的线性无关性来估计该维度，并得出在受限参数范围内，其期望维度以高概率等于 $\min\{n, k_1k_2\}$。本文旨在提供更通用且更显式的期望维度分析及方差分析，从而超越这些受限的参数范围。

方法论
作者建立了两个码的星积与双线性型求值之间的对应关系。具体而言，若 $C_1$ 和 $C_2$ 的生成矩阵分别为 $G_1$ 和 $G_2$，则星积 $C_1 \star C_2$ 被识别为作用在双线性型空间 $B = \text{Bil}(\mathbb{F}_q^{k_1}, \mathbb{F}_q^{k_2})$ 上的线性映射 $\psi_{G_1, G_2}$ 的像。星积的维度由 $k_1k_2 - \dim(\ker \psi_{G_1, G_2})$ 给出。

为了分析期望维度，作者专注于计算期望核的大小，即 $\mathbb{E}[|\ker \psi_{C_1, C_2}|]$。他们利用了一个概率模型，在该模型中，码是通过均匀随机选择系统生成矩阵的最后 $n-k$ 列来生成的。分析过程包括：

1. 枚举组合学： 计算具有特定秩 $r$ 且在生成矩阵的列上消失的（以矩阵表示的）双线性型的数量。这需要统计具有零对角线和特定零模式的矩阵。
2. 显式公式： 利用 $q$-二项式系数和包含排斥原理推导出期望核大小的显式公式（引理 3.5 和定理 str 3.9）。
3. 渐近分析： 研究当域大小 $q \to \infty$ 以及在特定增长条件下当代码维度 $k_1, k_2 \to \infty$ 时，这些公式的行为。
4. 方差分析： 利用导出的期望核大小的界限来上界化星积维度的方差。

核心贡献与结果

1. 显式下界： 本文提供了一个关于评估映射核大小的显式公式，从而为所有参数选择下的星积期望维度提供了一个显式的下界（推论 3.11）。这种方法不同于以往的秩-1 矩阵分析，它通过直接的组合计数提供了核的计数。

2. 域大小渐近性 ($q \to \infty$)：

   • 作者证明，随着域大小 $q$ 趋于无穷大，星积的期望维度渐近达到其最大可能值 $\min\{n, k_1k_2\}$，无论 $k_1$ 与 $k_2$ 之间的关系如何（推论 4.2）。
   • 具体而言，如果 $k_1k_2 < n$，期望核大小趋于 1；如果 $k_1k_2 = n$，趋于 2；如果 $k_1k_2 > n$，则趋于发散。
   • 维度的方差被证明渐近衰减至 0，其速率取决于 $k_1k_2 < n$ 还是 $k_1k_2 \ge n$（命题 4.3）。

3. 代码维度渐近性 ($k_1, k_2 \to \infty$)：

   • 在“容许”增长条件下（即 $k_1$ 和 $k_2$ 严格单调增长，且 $k_1k_2$ 相对于 $q^{k_1}$ 增长不过快），本文证明了期望核大小趋于稳定（定理 5.7）。
   • 因此，随着维度的增加，星积的期望维度以高概率达到 $\min\{n, k_1k_2\}$（推论 5.12）。
   • 在这些条件下，方差被证明渐近消失，若 $n < k_1k_2$ 或间隙 $n - k_1k_2$ 线性增长，则至少呈指数级衰减（命题 5.14）。

4. 与前人工作的比较： 将结果与 [19] 的秩-1 矩阵方法进行了比较。作者指出，其结果涵盖了更广泛的参数范围，特别是在较大的域大小 $q \ge 3$ 时，其对维度增长的界限比 [19] 中的界限更为严格（备注 5.13）。

意义与影响
该论文声称这些结果对以下领域有直接影响：

• 隐私信息检索 (PIR)： 在基于星积的 PIR 方案中，检索率受限于星积的维度。结果表明，虽然随机码渐近产生最大的星积维度（导致其检索率低于像 GRS 这样的结构化码），但在小域（例如 $\mathbb{F}_2$）上，采样具有次最大维度的码对仍存在非零概率。这意味着在无错误设置下，寻找有利的随机码对进行实验搜索是可行的。
• 安全分布式矩阵乘法 (SDMM)： 与 PIR 类似，SDMM 中的恢复阈值和落后者容忍度取决于星积维度。研究结果表明，随机构造通常无法实现渐近低的恢复阈值，但在实际实例中，针对有利参数仍可能找到合适的构造。
• 量子纠错： 本文讨论了二进制 CSS-T 码，这类码要求 $C_2 \subseteq C_1 \cap (C_1 \star C_1)^\perp$。结果表明，对于维度足够大的均匀随机码，星积 $C_1 \star C_1$ 很可能是大的，从而迫使正交补空间很小。这暗示使用随机 $C_1$ 构建高距离 CSS-T 码是不太可能的，因为由此产生的量子码其最小距离的下界会很弱。
• 密码分析： 星积维度被用作编码理论密码学（例如针对 Goppa 码）中的区分器。论文指出，虽然其结果证实了随机码通常具有最大的星积维度（使其能够与具有较小平方的结构化码如 Goppa 码相区分），但目前分析的特定参数范围并不威胁标准的 McEliece 系统的安全性。然而，该方法论为分析不同的代码对的星积以探索新的参数范围打开了大门。

结论
论文得出结论，随着域大小的增加，两个均匀随机码的星积期望维度渐近达到其理论最大值；并且在特定的增长条件下，随着代码维度的增加，该结论同样成立。在这些情形下，方差消失，表明存在测度集中现象。作者指出，推导方差的紧致下界以及对非渐近情况的分析是未来的开放性问题。