🔢 mathematics

A New Class of Linear Codes

本文介绍了一类通过乘法特征和超椭圆曲线构造的新型线性码，这类码在二进制域上实现了指数级规模，其相对距离渐近于 1/2，在与 Reed-Solomon 码级联时提供了改进的率-距离权衡，并因其具有随机性的平方性质和译码特性而展现出加密潜力。

原作者： Akash Bhople, Giacomo Cherubini, Giacomo Micheli, Tefjol Pllaha

发布于 2026-06-09

📖 1 分钟阅读🧠 深度阅读

原作者： Akash Bhople, Giacomo Cherubini, Giacomo Micheli, Tefjol Pllaha

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正试图通过一条充满噪声的电话线发送一条秘密信息。在编码理论的世界里，这条“信息”是一个数字字符串（称为码字），而“噪声”则是可能导致某些数字发生翻转的错误。为了确保信息能够准确送达，我们需要让这些码字之间彼此区别开来。如果两条信息太相似，一点点噪声就可能让它们看起来一模一样，从而让你无法分辨发送的是哪一条。

两个信息之间的距离是指它们在多少个位置上不同。速率是指你在总长度的信息中能装入多少实际的信息量。

这篇论文介绍了一种构建这些“秘密信息”码的新颖且巧妙的方法。作者 Akash Bhople 及其同事创造了一类新的线性码（一种具有特定、数学规律性的代码类型），这些代码在我们需要让信息彼此高度区分时，表现得比我们之前已知的最佳代码要出色得多。

以下是使用简单类比对他们发现的详细解读：

1. “影子”技巧

他们发明核心在于一个被称为**“影子码”（Shadow Code）**的东西。

想象你有一个巨大的、复杂的 3D 雕塑（一个被称为“超椭圆曲线”的数学曲线）。你从特定的角度向雕塑投射光线，它在墙上投射出一个影子。

雕塑： 这是一个涉及多项式（包含变量如 $x$ 的方程）的复杂数学函数。
影子： 作者将这个复杂的 3D 形状投影到 2D 墙面上。这个“影子”是一个简单的 0 和 1 的列表（二进制码）。
神奇之处： 他们投射影子的方式非常特殊。他们使用了一个名为“乘法特征”（可以理解为一种特殊的过滤器或透镜）的数学工具。这个过滤器观察雕塑并决定：“这个部分的形状是一个完全平方数吗？如果是，记为 0；如果不是，记为 1。”

由于原始雕塑如此复杂，且“光线”的投射方式非常特殊，由此产生的影子（即代码）具有两个惊人的特性：

它非常长： 它可以承载大量的数据。
它非常独特： 即使原始雕塑只有微小的差异，任何两个不同的影子看起来也会截然不同（高距离）。

2. 打败旧有的冠军

几十年来，这类代码的“冠军”被称为 Delsarte–Goethals 码。它们很优秀，但有一个局限：当你试图让信息变得更长时，你能发送的信息量（速率）会迅速下降，就像掉下陡峭的悬崖一样。

作者证明了他们的“影子码”就像是一个超级升级版。

类比： 如果说旧的代码像是自行车，那么新的代码就像是火箭。
结果： 对于相同的消息长度和相同的抗噪水平，新代码可以携带指数级更多的信息。用数学术语来说，如果旧代码能携带 100 个比特，新代码在同样的设置下可能会携带数百万甚至数十亿个比特。

3. “堆叠”增益（级联）

作者还展示了如何通过“堆叠”这些代码来使其变得更好。

想象你有一个强大且短小的代码（影子码）。
你使用另一个著名的代码（Reed-Solomon 码，用于 CD 和二维码）将许多这些短小的影子码组织在一起。
结果： 这创建了一个规模庞大且依然高效的码。论文声称，这种堆叠后的版本比将旧的 Delsante–Goethals 码与 Reed-Solomon 码进行堆叠要好得多。这就像是用更坚固的地基来建造摩天大楼；你可以盖得更高而不会倒塌。

4. 为什么这很重要（密码学）

论文提到了一个特定的应用领域：密码学（制作难以破解的秘密代码）。

在现代密码学中，有一个概念叫做代码的“平方”。如果你将两个来自你代码的消息以特定方式相乘，你会得到一组新的消息。
对于许多代码来说，这个“平方”是微小且可预测的，这使得它们容易受到攻击。
作者证明： 他们“影子码”的“平方”表现得像是一个随机的混乱状态。它变得巨大且不可预测。
类比： 如果坏人试图通过观察“影子的影子”来攻击你的代码，他们会发现一个极其混乱、看起来随机的混乱状态，这使得破解变得异常困难。这使得这些代码在创建数字签名方面非常有吸引力。

5. 如何读取信息（解码）

如果无法读回信息，那么代码就是毫无用处的。论文包含了一个用于解码这些信息的配方（由 Swastik Kopparty 提出的算法）。

问题： 你接收到一个带有噪声的影子，其中一些 0 变成了 1，反之亦然。
解决方案： 该算法将问题视为一个拼图。它尝试重建创建该影子的原始“雕塑”（多项式），即使影子已经受损。它使用一种巧妙的数学技巧来过滤掉噪声，从而找到原始的形状。

总结

作者构建了一种新型的数学“影子”，它具有以下特点：

比以往最好的代码都要大得多（指数级的提升）。
对噪声具有极强的鲁棒性。
难以被黑客破解，因为其数学结构在平方后看起来是随机的。
可以使用高效的算法进行解码。

他们通过将高级数论（有限域上的多项式）与曲线几何学相结合，投射出一个“影子”，从而将复杂的数学转化为一种超高效的通信工具。

技术摘要：一类新的线性码

问题陈述
本文研究了在有限域 $\mathbb{F}_r$ 上构造长度为 $n$ 、相对距离渐近于 $1/2$ （具体为 $d \approx n/2$ ）的线性码的构造问题。虽然最小距离约为 $n/2$ 的二进制码非常基础，但 Plotkin 界限限制了此类码的大小，使其在 $d \ge n/2$ 时极其微小。在 $d < n/2$ 但 $n - 2d = \Omega(\sqrt{n})$ 的情形下，已知最好的构造在历史上是非线性的 Delsarte–Goethals 码。这些码虽然有效，但其速率随长度增加而呈指数级衰减。作者旨在构造线性码，以实现与 Delsarte–Goethals 码相比相当甚至更好的参数，特别是针对在保持 $1/2$ 相对距离的情况下，实现代码规模（速率）的指数级提升。

方法论
作者引入了一种基于乘性特征和（multiplicative character sums）与超椭圆曲线理论的构造，称为影子码（Shadow Codes）。其核心策略包括：

域设置： 利用辅助域 $\mathbb{F}_q$ （其中 $q$ 是素幂数）来构造较小基域 $\mathbb{F}_r$ （其中 $r$ 是整除 $q-1$ 的素数）上的码。
超椭圆曲线： 选择一组在 $\mathbb{F}_q$ 上的单项不可约多项式集合 $P = \{p_1, \dots, p_L\}$ 。
特征映射： 定义一种映射，其中码字分量由在这些多项式的乘积上评估 $r$ 阶乘性特征 $\chi_r$ 来确定。具体而言，对于消息向量 $(v_1, \dots, v_L) \in \mathbb{F}_r^L$ ，在索引 $x \in \mathbb{F}_q$ 处的码字由 $\phi_r(\chi_r(\prod p_i(x)^{v_i}))$ 给出，其中 $\phi_r$ 是将单位根映射到 $\mathbb{F}_r$ 加法群的同构。
几何解释： “影子”是指超椭圆曲线 $y^r = f(x)$ （其中 $f$ 是这些多项式的乘积）在 $x$ 轴上的投影。码字的零点对应于 $f(x)$ 为 $r$ 次幂的 $x$ 坐标。
级联： 为了进一步优化参数，作者提出将这些影子码与 Reed-Solomon (RS) 码进行级联。

主要贡献与结果

影子码的构造： 论文证明了存在长度为 $n=q$ 、维数 $k \approx q^{1/2-\epsilon}$ 、最小距离 $d \ge \frac{r-1}{r}q - O(q^{1-\epsilon})$ 的 $\mathbb{F}_r$ -线性码。
- 定理 I.1： 确立了对于任何 $\epsilon \in (0, 1/2)$ 及足够大的 $q$ ，这些码的存在性。
- 推论 I.2： 特化为二进制码（ $r=2$ ），得到参数 $[q, \lfloor q^{1/2-\epsilon} \rfloor, d]$ ，其中 $d \ge q/2 - 2q^{1-\epsilon}$ 。
对 Delsarte–Goethals 码的指数级改进：
- 作者证明了在 $n - 2d = \Omega(\sqrt{n})$ 的情形下，其线性影子码的大小比 Delsarte–Goethals 码呈指数级更大。
- 命题 III.2： 表明对于一系列参数，影子码的大小与 Delsarte–Goethals 码之比为 $\Omega(2^{m\delta/2}/m^2)$ ，确认了指数级的增益。与 Delsarte–Goethals 码不同，新型码是线性的且拥有解码算法。
级联提升：
- RS-Shadow 级联（定理 V.1）： 通过将 Reed-Solomon 码与影子码级联，作者实现了一个长度为 $N = q^{n+1}$ 、维数为 $N^{1 - \frac{1}{2n+2} - \frac{2\epsilon}{n+1}}$ 且相对距离渐近于 $1/2$ 的码。
- 与 RS-RM 的比较： 论文指出，在标准级联中用影子码替换内层 Reed-Muller (RM) 码，可以在相同的长度和距离范围内获得显著更高的速率，因为影子码支持比一阶 RM 码更大的维数。
影子码的平方与密码学：
- 定理 VI.1： 证明了只要 $q$ 相对于维数 $L$ 足够大，影子码的平方（在 Schur 积下）的维数为 $L(L+1)/2$ 。这模拟了随机码的行为。
- 意义： 具有高维平方的码在密码学应用（如签名方案）中非常有价值，因为它们能够抵抗某些代数攻击。相比之下，论文显示（定理 VI.4）级联 RS-RM 码的平方其维数相对于通用界限是微乎其微的，因此不太适合此类应用。
解码算法：
- 第七节： 论文提出了基于 Swastik Kopparty 方法的高效二进制影子码解码算法。这涉及从二次特征的有噪评估中恢复无平方因子消息多项式，利用线性代数和多项式分解技术。
在数论中的应用：
- 第四节： 作者应用编码理论界限（Plotkin 和 McEliece）推导出关于指数和的新结果，具体建立了关于有限域上某些特征和最大值的下界。

重要性与主张
该论文声称提供了一个构造性证明，证明了一类新的线性码的存在性，这类码在相对距离为 $1/2$ 的情形下优于长期存在的非线性 Delsarte–Goethals 码。其主要意义在于，在保持线性并提供显式解码算法的同时，实现了码规模（速率）的指数级提升。此外，论文强调了这些码的代数结构（特别是其平方的行为）使其成为极具前景的密码学应用候选对象，这使它们区别于其他级联码族（如 RS-RM）。这项工作通过推导特征和的新界限，架起了编码理论与数论之间的桥梁。