🔢 mathematics

List-Decoding Counterexamples Yield Lower Bounds on Mutual Correlated Agreement Error

本文证明了列表译码失败的显式反例可以被构造性地转化为具有可证明的高互相关一致性误差的码，从而在代数几何码和 Reed-Solomon 码中，在列表译码失败与该特定误差指标的下界之间建立了直接联系。

原作者： Yiwen Gao, Hong Yang, Yang Xu, Haibin Kan

发布于 2026-07-14

📖 1 分钟阅读🧠 深度阅读

原作者： Yiwen Gao, Hong Yang, Yang Xu, Haibin Kan

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

想象一下你是一名正在试图抓捕一群间谍（码字）的侦探，他们正试图溜过一个安全检查站（代码）。在数字通信的世界里，这些“间谍”实际上是由于噪声而略微变得混乱的消息。通常情况下，如果一条消息偏离正确模式太远，安全系统会说：“不对，这不是一条有效消息，”然后将其丢弃。

但有时，情况会变得很棘手。想象这样一个场景：一条被扰乱的消息竟然同时在多个不同的有效间谍模式中都显得非常接近。在编码理论的世界里，这被称为列表译码反例（list-decoding counterexample）。这就像是在人群中发现了一个嫌疑人，他看起来既像这个人，又像那五个人。如果发生这种情况，标准的安全检查可能会感到困惑，并说：“好吧，也许他是其中之一。”

这篇由 Gao Yiwen、Yang Hong、Xu Yang 和 Kan Haibin 撰写的论文，探讨了一个特定且高风险的版本。他们研究的是一种名为**互相关一致性（Mutual Correlated Agreement）**的安全测试。你可以把这个测试想象成：检查一组被扰乱的消息在随机混合在一起（比如把五种不同的奶昔搅拌成一种）后，是否仍然看起来像是一个有效的间谍模式。

重大发现：“坏的混合”配方

作者们证明了一个非常具体的、具有构造性的事实：如果你能找到一个列表译码反例（即一条看起来过于接近许多有效码字的消息），你就可以利用它来构建一个新的、略有不同的代码，而这个新代码保证会使“互相关一致性”测试失败。

这里使用了厨房类比来解释这个神奇的技巧：

准备阶段： 你有一组 $L+1$ 个不同的“有效”配方（码字），它们尝起来都与一个奇怪的、被扰乱的菜肴（接收到的词）惊人地相似。
扩展阶段： 作者将原始代码中的每个配方增加了一个额外的“配料”（坐标）。他们创建了两个特殊的菜肴， $\pi_0$ $π_{0}$ 和 $\pi_1$ $π_{1}$ 。
- $\pi_0$ 是原始的扰乱菜肴，但在末尾添加了一个零。
- $\pi_1$ 是一个全为零的菜肴，除了末尾的一个“1”。
混合阶段： 现在，想象用一个秘密的香料量 $\alpha$ $α$ 将这两个菜肴混合在一起。新的菜肴是 $\pi_0 + \alpha \cdot \pi_1$ $π_{0} + α \cdot π_{1}$ 。
- 在原始部分的菜肴中，它看起来仍然像那个被扰乱的词。
- 在末尾处，它的味道正好等于香料量 $\alpha$ 。
陷阱： 因为原始的扰乱词与 $L+1$ 个不同的有效配方都很接近，所以存在 $L+1$ 个特定的香料量（ $\alpha$ 值），会让混合后的菜肴看起来完美地符合其中一个有效配方（包括新增的配料）。
故障： 然而， $\pi_0$ 和 $\pi_1$ 这两个菜肴本身在这一组更大的配料集上并不与该代码共享共同模式。这意味着混合过程创造了一个本不该存在的“虚假”一致性。

论文证明，如果拥有 $L+1$ 个附近的码字，你可以找到至少一定数量的这些“坏的香料量”（坏的组合点）。具体来说，坏点的数量至少为：
$\left\lceil \frac{(L+1)q}{q+L} \right\rceil$
其中 $q$ 是“口味调色板”（有限域）的大小。

“抽取与附加”的神奇技巧

这里有一个问题。添加那个额外的配料让菜肴变大了（代码长度增加了）。但在现实世界中，你不能随意改变消息的大小；它必须保持相同的长度。

作者执行了一个巧妙的“抽取并附加（Puncture and Append）”动作：

抽取（Puncture）： 他们从原始代码中移除一个不会破坏代码结构的配料（坐标）。这使得代码稍微变小了一点。
附加（Append）： 他们添加了之前找到的那个新的“坏”配料。
结果： 代码回到了原始的大小！

论文表明，这个新代码 $C'$ 与旧代码几乎完全相同。它可能会损失一点点“安全裕度”（最小距离最多减少 $1/n$ ），但它保证在互相关一致性测试中具有高错误率。事实上，错误概率至少为：
$\frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$

保持形状：保结构代码

作者并没有止步于此。他们知道在现实生活中，代码通常具有特殊的形状，比如 Reed-Solomon 码（用于 CD 和二维码）或 代数几何（AG）码。这些代码不仅仅是随机的数字列表；它们是使用特定的数学映射（如在特定点评估多项式）构建的。

论文指出，你不能只是随便扔进一个随机的配料；它必须符合配方。作者证明，你仍然可以在保持代码特殊结构完整的同时，执行“抽取并附加”的技巧。

对于 Reed-Solomon 码，你只需用另一个评估点替换掉原来的一个评估点。
对于 AG 码，你用另一个“位置”（几何形状上的点）替换掉原来的一个“位置”。

他们证明，即使在这些严格的规则下，如果原始代码存在列表译解码反例，你仍然可以构建一个属于同一家族的新代码，该新代码在互相关一致性测试中会以保证的错误率失败。

这篇论文没有说什么

了解这篇论文没有在做什么也很重要：

它并不是说这些代码在所有用途下都是失效的。它只是表明，如果存在特定的“列表译解码反例”，那么特定的“互相关一致性”失败就必然存在。
它并不是声称要解决这个问题。相反，它通过构建一个反例来证明，在这种特定情况下，错误概率无法被降得任意小。这是一个关于“不可能实现让错误率为零”的证明。
它并不是暗示这对每一个代码都适用。它仅适用于当你已经能找到一个列表译解码反例（即一条接近 $L+1$ 个码字的消息）时。

他们有多大的把握？

作者非常有信心。他们不仅仅是在猜测或通过计算机进行模拟。他们提供了一个构造性证明。这意味着他们不仅是说“这可能是可能的”；他们还给出了一个构建新代码以及证明错误存在的步骤（算法）。

他们明确指出，给定一个接收到的词和 $L+1$ 个附近的码字，该构造过程会显式地产生新的代码和见证词。这是一个坚实的数学事实，而不是一种建议。

给好奇青少年的总结

把这篇论文看作是一场关于“如何利用漏洞破坏特定类型的安全测试”的高级课程。

漏洞： 如果一条消息接近太多有效的码字（ $L+1$ ），系统就已经陷入麻烦了。
破解： 作者展示了你可以利用这种麻烦，通过混合另外两个消息来创造一个“虚假”的有效消息。
结果： 你可以证明这种混合测试的错误率至少是 $1/q$ 乘以一个涉及 $L$ 和 $q$ 的特定数值。

论文的核心思想是：“如果你拥有一个列表译解码反例，你就不能声称你的代码在面对这些混合攻击时是绝对安全的。以下是构建这种攻击的具体方法，以及错误会有多大。”

对于 Reed-Solomon 码（你二维码中使用的那种），其错误率下界变为：
$\frac{1}{q} \left\lceil \frac{(L+1)q}{q+L(k-1)} \right\rceil$
其中 $k$ 是代码的维数。

论文得出结论，列表译解码性与互相关一致性之间的关系是非常紧密的：如果其中一个失败了，另一个也必然会失败，并且这里有精确的数学公式来证明这一点。

技术摘要：列表译码反例产生互相关一致性误差的下界

1. 问题陈述

本文探讨了线性码背景下**互相关一致性（Mutual Correlated Agreement, MCA）**这一基本问题。MCA 是批量接近性测试（batched proximity testing）中实现健全性的关键属性，而这种测试机制被广泛用于简洁非交互式知识论证（SNARKs）和交互式近邻证明（IOPPs）。

具体而言，MCA 研究的是：一个随机线性组合生成的接收词，是否会由于原始词之间的相关一致性结构之外的原因，从而伪造出一个巨大的一致性域。虽然对于各种代码族在某些界限内已存在正向结果（接近性间隙），但仍需理解其局限性：即当一个码不具备列表译码性（list-decodable）时，误差概率（即“坏”组合点出现的可能性）最高可以达到多少。

核心问题在于建立一种构造性的联系，将列表译码反例（即在一定距离内拥有超过 $L$ 个码字的接收词）与 MCA 误差的下界联系起来。前人的工作已经展示了列表译码性与相关一致性之间的联系，但本文旨在提供一种通用的、构造性的方法，从列表译码失败中推导出显式的 MCA 误差下界，并保持该代码族的结构特性。

2. 方法论

作者采用了一种以**“挖补与附加”（puncture-and-append）**技术为核心的构造性方法。该方法分为三个逻辑阶段：

域外扩展（Out-of-Domain Extension）：
从一个不是 $(p, L)$ -列表可译码的线性码 $C$ 开始，作者确定一个接收词 $y$ 以及 $L+1$ 个位于距离 $p$ 以内的不同码字 $c_1, \dots, c_{L+1}$ 。他们通过附加一个新的坐标，构造了一个长度为 $n+1$ 的扩展码 $C'$ 。
- 在扩展域上定义了两个词 $\pi_0$ 和 $\pi_1$ 。 $\pi_0$ 携带原始接收词 $y$ （附加一个零），而 $\pi_1$ 在原始域上为零，在新的坐标上为 1。
- 作者利用线性代数碰撞界限（引理 1）来选择一个向量 $a$ （定义生成矩阵的附加列），使得值 $m_i \cdot a^T$ （其中 $m_i$ 是临近码字的度量向量）包含大量不同的值。
- 每个不同的值都对应一个“坏的组合点” $\alpha$ ，在该点处，线性组合 $\pi_0 + \alpha \pi_1$ 与一个扩展码字在很大的一组集合上达成一致，但它并不具备与原始对（pair）的相关一致性。
挖补与附加（长度保持）：
为了确保生成的代码具有与原码相同的块长度 $n$ ，作者在附加新坐标之前，先从原码中挖补（移除）一个坐标。
- 他们证明了如果原码不是 $(p, L)$ -列表可译码的，则存在一个坐标，其移除后能保持维数以及非列表可译码的性质（仅需对相对距离参数进行微调）。
- “挖补一个，附加一个”的过程产生了一个长度为 $n$ 的代码 $C'$ ，它保留了扩展步骤中推导出的大量坏组合点。
结构保持泛化（Structure-Preserving Generalization）：
为了将此方法应用于特定的代码族（如 Reed-Solomon 或代数几何码），作者将构造过程推广到了索引代码族。
- 作者不再选择任意向量作为附加列，而是通过映射 $v: \Omega \to \mathbb{F}_q^k$ 从有限集 $\Omega$ 中选择一个索引。
- 他们引入了索引集上的碰撞界限 $\lambda$ ，以确保不同的消息不会在可用索引上过于频繁地发生碰撞。这使得构造过程能够保持在同一个代码族内（例如，仅改变代数几何码中的一个求值点），同时保留 MCA 误差的下界。

3. 核心贡献与结果

定理 1（一般线性码）：
本文确立了：若线性码 $C$ 的维数为 $k$ ，长度为 $n$ ，且不是 $(p, L)$ -列表可译码的（其中 $p < \Delta(C) - 1/n$ ），则存在一个相关的同长度、同维数代码 $C'$ ，满足：
$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)q}{q+L} \right\rceil$
此外， $C'$ 的相对最小距离满足 $\Delta(C') \geq \Delta(C) - 1/n$ 。如果 $C$ 的最小权重码字没有覆盖所有坐标，则距离可以被精确保持（ $\Delta(C') \geq \Delta(C)$ ）。该构造是显式的，同时生成了代码 $C'$ 以及见证误差的一对词。

定理 2（结构保持版本）：
对于由列映射 $v$ 索引的代码族 $\Omega$ ，假设存在碰撞界限 $\lambda$ （即任何非零向量 $u$ 最多有 $\lambda$ 个索引 $\omega$ 满足 $u \cdot v(\omega)^T = 0$ ），该构造产生的代码 $C'$ 属于同一族。

$C'$ 与 $C$ 仅在一个坐标索引上有所不同。
MCA 误差下界为：
$\text{err}_{\text{MCA}}(C', p) \geq \frac{1}{q} \left\lceil \frac{(L+1)N}{N+L\lambda} \right\rceil$
其中 $N = |\Omega|$ 。

特定代码族的推论：

代数几何（AG）码： 通过将 $\Omega$ 设为有理点集并将 $\lambda = \deg(G)$ ，作者表明，如果一个 AG 码不是列表可译码的，可以通过修改至多一个位置的求值除子 $D$ 来获得具有指定 MCA 误差下界的码。所得码仍处于相同的函数域和 Riemann-Roch 空间内。
Reed-Solomon (RS) 码： 作为一种特例（其中 $\Omega = \mathbb{F}_q$ 且 $\lambda = k-1$ 为多项式次数），该结果给出了误差下界 $\frac{1}{q} \lceil \frac{(L+1)q}{q+L(k-1)} \rceil$ 。这证实了 RS 码中的列表译码失败直接意味着显著的 MCA 误差。

4. 意义与主张

本文声称提供了一种构造性且通用的方法，将列表译码的反例转化为互相关一致性误差的下界。

与前人工作的对比： 作者指出，前人的工作（如 Ben-Sasson 等人，Crites 和 Stewart）使用诸如除以 $X-\beta$ 之类的特定操作来推导 Reed-Solomon 码的类似下界，而这些操作本质上改变了码的次数（从 $k$ 到 $k+1$ ）。相比之下，本文的构造保持了代码的维数和块长度，并且适用于任意线性码，无需进行次数偏移。
结构完整性： 一个重要的贡献是能够在仅修改单个坐标的同时，保持代码的结构族（例如，使 AG 码仍然是同一空间上的 AG 码）。这对于那些由底层代数结构固定的代码族应用场景至关重要。
健全性影响： 通过显式构造出具有高 MCA 误差的码，本文量化了批量接近性测试中健全性的极限。它表明，如果一个码不是列表可译码的，则无法保证随机线性组合以高概率远离该码；具体而言，误差概率被下界公式所限制。

这项工作并未提出新的实验协议或超出为 AG 和 RS 码实例化该原理之外的未来应用。其主要贡献在于理论层面：在列表译码属性与互相关一致性误差界限之间建立了一座严谨且构造性的桥梁。