🔢 mathematics

The Closure of LCD-to-GI Reductions via Generalized Inner Products

本文确立了将线性码的置换等价问题归约至图同构问题的正交投影法的精确闭包，证明了此类归约可行当且仅当码的核维数至多为 1（在特征为 2 时具有特定条件），并针对这些情形提供了精确的计数公式及多项式时间算法。

原作者： Keita Ishizuka

发布于 2026-05-25

📖 1 分钟阅读🧠 深度阅读

原作者： Keita Ishizuka

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

想象你有两个秘密代码，就像两种不同的扑克牌排列方式。置换等价问题（PEP） 提出了一个简单的问题：“这两副牌是否只是同一副牌，只是洗牌顺序不同？”

在密码学和编码理论的世界中，解决这一问题就像寻找一把隐藏的钥匙。如果你能证明这两个代码仅仅是彼此的洗牌版本，你就破解了一个重大谜题。如果不能，它们就是根本不同的。

很长一段时间以来，数学家们拥有一种强大的工具来解决这个谜题，但它仅适用于一种非常特定类型的代码，称为LCD 码（线性互补对偶码）。可以将 LCD 码想象为“完美平衡”的牌组，其中没有任何一张牌会意外地重复另一张，从而扰乱数学运算。他们使用的工具是图同构求解器——一种超级智能的计算机程序，用于检查两个复杂的图形（图）是否具有相同的形状，只是标签不同。

该工具的工作原理是将代码转化为一种“阴影”（在数学上，即正交投影器）。如果两个代码的阴影看起来像同一个图，那么这些代码就是等价的。但这里有一个陷阱：如果代码不是完美平衡的（即如果它有一个“核”，或者说存在混乱的重叠），这个工具会立即失效。

重大发现：扩展工具箱

Keita Ishizuka 的这篇论文提出了一个大胆的问题：“我们能把这个‘阴影工具’推多远？我们能否让它也适用于混乱、不平衡的代码？”

作者试图通过改变我们观察代码的“透镜”来修复这个工具。他没有使用标准的距离测量方式（标准内积），而是尝试使用由矩阵 $M$ 代表的一整套不同的透镜。

“魔法透镜”的发现

论文证明，你不能随意挑选任何透镜。大多数透镜会严重扭曲图像，导致阴影不再反映真相。然而，作者发现了一个非常具体、神奇的透镜家族是有效的。

想象透镜是混合配料的食谱。论文证明，唯一有效的食谱是那些混合了以下内容的：

单位矩阵（ $I$ ）： 保持一切原样。
全 1 矩阵（ $J$ ）： 在混合中加入一点“每个人与每个人相连”的元素。

在数学上，透镜必须呈现为 $M = aI + bJ$ 的形式。这就像是在说：“要看清真相，你必须透过一个混合了‘自我’与‘群体’的滤镜来观察代码。”如果你尝试任何其他滤镜，魔法就会失效，工具也会失败。

“核”的限制

即使有了这个魔法透镜，也存在一个硬性限制。论文确立了一个“闭包”，意味着这是该方法所能达到的绝对边界。

规则： 该工具仅在代码的“混乱程度”（即其核）非常小时才有效。具体来说，混乱程度必须为零（完美平衡）或一（微小的重叠）。
壁垒： 如果代码的“核”大小为 2 或更大（即一个巨大且纠缠的混乱体），该方法就会撞上砖墙。无论你如何调整透镜，都无法将这些代码转化为图来解决谜题。它们完全超出了这种特定技术的触及范围。

特殊情况：二进制世界

论文还指出了二进制代码世界（即一切仅为 0 和 1，如标准计算机中）的一个怪癖。在这个特定的世界里，核大小为 1 的“混乱”代码实际上会消失。因此，对于二进制代码，该工具仅适用于完美平衡的代码。在这个特定的宇宙中，“魔法透镜”无法帮助你解决那些混乱的代码。

结果：计数与求解

作者并没有止步于发现限制，他还做了另外两件事：

统计“赢家”： 他创建了一个精确的公式，用于计算究竟有多少个代码可以通过此方法求解。这就像确切知道一大串钥匙中有多少把能打开特定的锁。他使用了高级数学（特征和与二次型）将这些数字精确到最后一位。
算法： 他编写了一个供计算机遵循的分步食谱（算法）。
- 首先，检查代码是否过于混乱（核大小 $\ge$ 2）。如果是，则放弃。
- 如果足够小，则尝试“魔法透镜”食谱（$aI + bJ$）。
- 将代码转化为图。
- 运行图匹配程序。
- 如果图匹配，则代码是等价的。

总结

简单来说，这篇论文在沙地上划出了一条清晰的界线。它指出：“我们可以使用一种非常特定类型的数学透镜，解决那些要么完全干净、要么只有一点点划痕的代码的‘洗牌牌组’谜题。但如果代码过于混乱，这种特定方法将永远无法奏效，无论怎么做。”

它关闭了试图强行让这种特定工具在混乱代码上生效的大门，通过告诉研究人员如果遇到那些更大、更混乱的代码应寻找完全不同的策略，从而为他们节省了时间。

技术摘要：基于广义内积的 LCD 到 GI 归约的封闭性

1. 问题陈述

线性码的**置换等价问题（PEP）**询问两个给定的线性码是否在坐标置换下相同。该问题对于线性码的分类以及基于码的密码学（例如 LESS 签名方案和 SPECK 方案）的安全性分析至关重要。

PEP 的复杂度与**图同构（GI）**问题密切相关。虽然 PEP 通常被认为很难，但 Bardet 等人 [3] 的一项重大突破表明，**线性互补对偶（LCD）**码（即具有平凡核的码，即 $C \cap C^\perp = \{0\}$ ）的 PEP 可以在多项式时间内归约到 GI。该归约通过正交投影子 $\Pi_C = G^T(GG^T)^{-1}G$ 将 LCD 码映射为加权图。

然而，该方法依赖于 Gram 矩阵 $GG^T$ 是非奇异的，这将其适用范围限制在 LCD 码。具有非平凡核（即 $\dim(\text{Hull}(C)) \ge 1$ ）的码无法通过此特定构造进行处理。本文解决的核心问题是：正交投影子方法可以扩展到何种程度？ 具体来说，能否通过使用不同的双线性形式将其推广到具有非平凡核的码，如果是这样，此类归约的确切结构限制是什么？

2. 方法论

作者将标准内积推广为由结构矩阵 $M$ 表示的任意非退化对称双线性形式。

广义投影子：他们定义了 $M$ -对偶码 $C^{\perp_M}$ 和 $M$ -核 $\text{Hull}_M(C)$ 。对于 $M$ -LCD 码（其中 $\text{Hull}_M(C) = \{0\}$ ），他们构造了一个广义正交投影子：
$\Pi_{C,M} = M G^T (G M G^T)^{-1} G$
归约条件：归约的核心依赖于恒等式 $\Pi_{CP, M} = P^T \Pi_{C,M} P$ ，其中 $P$ 是置换矩阵。该恒等式确保如果两个码是置换等价的，那么它们的投影子作为加权图是同构的。
$M$ 的特征化：作者研究了哪些结构矩阵 $M$ 满足对所有置换 $P$ 都有 $P M P^T = M$ （或其标量倍数）的条件。这是确保投影子在置换下表现正确的必要条件。
枚举与算法：利用二次型上的特征和（特别是 Weil 定理），作者推导出了可归约码数量的精确枚举公式。他们还构建了一个多项式时间算法，试图寻找合适的 $M$ 将给定的一对码归约到 GI。

3. 主要贡献与结果

A. 有效结构矩阵的特征化（定理 3.5）
本文证明，正交投影子方法产生有效归约（ $C_1 \cong C_2 \iff \Pi_{C_1, M} \cong \Pi_{C_2, M}$ ）当且仅当结构矩阵 $M$ 具有如下形式：
$M = aI + bJ$
其中 $I$ 是单位矩阵， $J$ 是全 1 矩阵，且 $a, b \in \mathbb{F}_q$ 满足非退化条件（ $a \neq 0$ 且 $a + nb \neq 0$ ）。没有其他非退化对称双线性形式允许这种归约。这确立了正交投影子方法的封闭性：人们不能通过选择任意双线性形式来扩展该方法；该形式必须是单位矩阵和全 1 矩阵的线性组合。

B. 可归约码的完整特征化（定理 4.5）
作者确定了哪些码允许此类归约：

码 $C$ $C$ 通过此方法可归约到 GI，当且仅当：
1. $C$ 是 LCD 码（标准情况， $M=I$ ），或者
2. $\dim(\text{Hull}(C)) = 1$ 且唯一的核向量 $x$ 满足 $(x, \mathbf{1}) \neq 0$ （其中 $\mathbf{1}$ 是全 1 向量）。
特征 2：在特征为 2 的域中，核中任何向量都不满足条件 $(x, \mathbf{1}) \neq 0$ （因为 $(x, x) = (x, \mathbf{1})^2 = 0$ 意味着 $(x, \mathbf{1}) = 0$ ）。因此，在特征 2 中，只有 LCD 码是可归约的。
高核的不可行性：对于 $\dim(\text{Hull}(C)) \ge 2$ 的码，无论选择何种 $M = aI + bJ$，都证明不可通过正交投影子方法归约。

C. 枚举公式（定理 5.3）
本文提供了计算 GI 可归约 $[n, k]_q$ 码数量（针对奇数 $q$ ）的精确公式。该计数是以下两项之和：

标准 LCD 码的数量 $L(n, k, q)$ 。
满足坐标和条件的核维度为 1 的码的数量，这是利用具有非零坐标和的各向同性向量的计数以及具有特定判别式的商空间上 LCD 码的质量公式推导得出的。

D. 归约算法（第 6 节）
提出了一个多项式时间算法：

检查核维度。如果 $\ge 2$ ，输出“不可归约到 GI"。
如果是 LCD 码，使用 $M=I$ 。
如果核维度为 1，搜索标量 $b$ ，使得 $M = I + bJ $使两个码都成为$ M$-LCD 码。
构造广义投影子并求解由此产生的图同构问题。

4. 意义与主张

本文声称提供了正交投影子方法能力的完整特征化。

封闭性：它明确关闭了使用此特定技术将 Bardet 等人的归约扩展到具有大核（ $\ge 2$ ）的码的大门。它证明了该方法本质上仅限于核维度至多为 1 的码（在特征 2 中仅限于 LCD 码）。
结构限制：它确定了归约生效所需的特定代数结构（$M = aI + bJ$），表明没有其他对称双线性形式可以促进这种映射。
密码学影响：这些结果为选择基于码的密码方案（如 SPECK）的参数提供了标准，以确保它们具有 $\ge 2$ 的核维度，从而使其超出此特定 GI 归约攻击向量的范围。

作者最后提出了一个开放性问题：是否存在其他不基于正交投影子的归约策略，能够将 $\dim(\text{Hull}(C)) \ge 2$ 的码的 PEP 映射到 GI，或者此类归约是否被证明是不可能的。