🔢 mathematics

Breaking ACDGV MinRank Gabidulin encryption schemes over matrix codes

本文提出了一种多项式时间密钥恢复攻击，通过结合组合与代数技术来恢复等效密钥，从而破解了增强型加比迪林矩阵码（EGMC）加密方案中所有提出的参数集，将声称的 128 位安全性降低至仅 35 位。

原作者： Thai Hung Le

发布于 2026-08-05

📖 1 分钟阅读🧠 深度阅读

原作者： Thai Hung Le

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

想象一下，互联网是一个繁忙的大都市，每个人都试图发送秘密信息。为了保护这些信息不被窥视，我们使用被称为“加密”的数字锁。长期以来，科学家们一直在利用复杂的数学谜题来构建这些锁，这些谜题易于创建，但在没有密钥的情况下极难破解。最近，一种新的锁被提了出来，它使用一种涉及数字网格和“秩”（rank，这只是衡量网格内实际包含多少信息的一种高级说法）的特殊数学类型。这些新锁的设计者认为，他们增加了一层“噪声”——就像收音机里的静电干扰一样——来隐藏锁的真实形状，使其在试图破解它的人眼中看起来像是一团随机的混乱。他们声称这种设计非常安全，即使是超快速的量子计算机也无法破解它，并且他们承诺它会非常小巧且高效，非常适合未来的安全通信。

然而，就像一个依赖特定手法的小魔术一样，这种新锁有一个隐藏的缺陷。研究人员 Thai Hung Le 发现，这种“噪声”并没有像大家想象的那样有效地隐藏秘密形状。通过结合巧妙的猜测和代数侦探工作，研究人员找到了一种方法，可以剥开静电层的外壳，揭示出底层的原始结构。这就像有人建造了一座带有秘密蓝图的纸牌屋，并在上面覆盖了一层雾气，但人们意识到，如果从正确的角度观察这层雾，蓝图仍然隐约可见。这一发现意义重大，因为这意味着这些新锁并不像宣传的那样安全，设计者们需要在开始用它们保护数据之前，重新思考他们的蓝图。

这篇论文的重要发现

在这篇论文中，Thai Hung Le 展示了一种破解“增强型 Gabidulin 矩阵码”（Enhanced Gabidulin Matrix Code, EGMC）加密方案的新方法。这些方案最近被引入，旨在创造一种非常小巧、高效的加密密钥，使其能够抵御来自未来量子计算机的攻击。这些方案的安全依赖于这样一个假设：如果你取一个特殊的、有结构的数字网格，并加入随机的行和列（即“噪声”），它就会变得与完全随机的混乱无法区分。

作者表明这个假设是错误的。攻击者并不需要尝试穷举每一种移除噪声的方法（这会耗费极长时间），而是引入了一种“混合”攻击。想象一下，你正在试图在一个巨大的、被打乱的马赛克中寻找特定的图案。旧的方法是猜测每一个瓷砖的位置。而这种新方法更聪明：它只猜测其中一行瓷砖的位置，然后利用数学方法立即计算出其他瓷砖必须在什么位置。

论文详细介绍了两种主要方法：

猜测列： 攻击者猜测网格的列是如何被打乱的，然后利用代数求解行是如何被打乱的。
猜测行： 攻击者猜测行的打乱方式，然后求解列的打乱方式。

一旦攻击者弄清楚了打乱方式，他们就可以剥离掉随机噪声，揭示出原始的隐藏结构。论文证明，这个结构是一个“Gabidulin 码”，这是一种一旦你知道了秘密模式就非常容易解决的数学谜题。

这篇论文实际上破解了什么

作者不仅找到了一个小裂缝，而是直接砸碎了整扇窗户。论文证明，这种攻击对 EGMC 加密方案中提出的全部 16 组参数集都有效。这意味着该方案建议使用的所有版本的锁现在都被认为失效了。

为了让你了解其效力，论文研究了一组原本旨在提供 128 位安全性（一种标准安全水平）的数字。作者展示了这种攻击如何将安全性降低到仅剩 35 位。在加密领域，这就像是从一个拥有百万位组合的保险库变成了一个小孩就能在几秒钟内解开的锁。

论文提供了一个具体的例子来展示这种威力：利用他们的方法，研究人员在不到 10 分钟的时间内就恢复了那个 128 位安全级别的密钥。这不仅仅是一个理论上的想法；他们还为此编写了一个计算机程序。

这篇论文排除了什么

需要注意的是，这篇论文说明了哪些方法是不起作用的。作者解释说，以往破解这些代码的尝试依赖于“组合”方法，即同时猜测行和列的打乱情况。论文认为，与这种新的“混合”方法相比，旧的方法太慢且效率低下。

此外，论文反对“仅仅通过增大参数（增加更多噪声）就能解决问题”的观点。作者指出，对于某些类型的此类代码——特别是当其中一个噪声因子（即额外的行数或额外的列数）为零时——攻击会变得如此之快，以至于可以在“多项式时间”内完成。这意味着在这些特定情况下，无论你如何增加锁的大小，攻击速度依然快到足以破解它。论文建议，唯一的潜在修复方法是改变基本设计，使两个噪声因子都为非零且足够大，以阻止攻击，但作者警告说，这可能会使密钥和消息变得过于庞大而失去实用价值。

他们有多确定？

论文对其结果非常有信心。作者不仅是在猜测，还提供了关于其攻击方式如何运作的完整数学证明，并辅以可运行的计算机实现。他们明确指出，其攻击破坏了该方案的所有提议版本。他们还将其结果与之前的攻击进行了对比，表明其方法显著更快、更强大。论文结论认为，EGMC 加密方案不再安全，安全界需要转向其他的设计。

技术摘要：通过矩阵码破解 ACDGV MinRank Gabidulin 加密方案

问题陈述
本文探讨了增强型 Gabidulin 矩阵码（EGMC）的安全性。EGMC 是由 Aragon 等人在 Asiacrypt 2024 上提出的一种掩码方案，旨在隐藏 Gabidulin 矩阵码的代数结构，从而实现紧凑的 McEliece 型和 Niederreiter 型加密方案，其具有极小的密文体积（例如，针对 128 位安全性的密文仅为 65 字节）。EGMC 的安全性依赖于“判定性 EGMC 不可区分性问题”：即假设被掩码后的 EGMC 码在计算上与随机矩阵码不可区分。此前的密码分析（特别是 Porwal 等人在 Eurocrypt 2026 上提出的基于 MinRank 的核攻击）展示了指数级时间的攻击，虽然破解了部分提议的参数集，但仍有部分参数集保持安全。本文作者研究了 EGMC 构造是否保留了足够的隐藏结构，从而使其能被更高效地破解。

方法论
作者提出了一种新的“混合”区分器以及随后的密钥恢复攻击，该攻击结合了组合猜测与代数求解。不同于以往通过暴力搜索行压缩矩阵和列压缩矩阵的区分器，本攻击仅通过猜测其中一个压缩矩阵，并利用代数技术求解另一个。

该攻击主要有两个方向：

猜 $V$ 解 $U$ (Guess- $V$ -solve- $U$ )：攻击者猜测列压缩矩阵 $V$ ，并代数求解行压缩矩阵 $U$ 。
猜 $U$ 解 $V$ (Guess- $U$ -solve- $V$ )：攻击者猜测行压缩矩阵 $U$ ，并代数求解列压缩矩阵 $V$ 。

代数建模与求解
一旦猜中一个有效的压缩矩阵，公钥码将被压缩为一个等价于短 Gabidulin 码（具体为 $[k+1, k]$ 码）的子空间。作者将“该压缩码必须是由特定向量湮灭的 $F_{q^m}$ -超平面”这一条件进行建模。这导致了一个双线性方程组，在经过线性化后，产生了一个在扩域 $F_{q^m}$ 上的齐次线性方程组。

攻击的核心在于寻找该线性系统核中的秩-1 解。作者观察到，该核存在一个元素位于基域 $F_q$ 中的基。因此，问题转化为寻找一个能产生秩-1 矩阵的基矩阵的线性组合。这被公式化为一个二次方程组（通过消失的 $2 \times 2$ 小行列式来表达）。

为了高效求解该二次方程组，作者采用了用于零维多项式系统的特征值方法（Stickelberger-Eigenvalue 方法）。他们利用核的 Frobenius 稳定性，在较小的基域 $F_q$ 上进行计算，而非在扩域 $F_{q^m}$ 上，从而显著降低了复杂度。一个关键猜想（猜想 1）指出，由小行列式生成的理想的商代数维度等于 $m$ ，这确保了系统是零维的，并且可以通过特征值法求解。

核心贡献

混合区分器：本文引入了一种区分器，通过代数求解一个压缩矩阵，避免了以往方法中完整的暴力搜索成本。
多项式时间密钥恢复：作者证明，如果附加因子 $\ell_1$ 或 $\ell_2$ 其中之一为零，则攻击变为多项式时间。这是因为指数级的猜测因子消失了，只剩下代数求解步骤，从而能够高效恢复隐藏的压缩矩阵。
码扩展：在恢复出一个被截断（短）的 Gabidulin 码后，作者提供了一种多项式时间算法，通过利用 Gabidulin 码的 $q$ -Frobenius 结构，将该码扩展回全长的等效秘密 Gabidulin 码。
通用解密：恢复出的等效秘密密钥（陷门）允许对 EGMC-McEliece 和 EGMC-Niederreiter 形式的密文进行解密。

结果
该攻击破解了所有 16 组提议用于 EGMC-Niederreiter 加密的参数集。

安全性削减：对于针对 128 位安全性设计的参数集 $(2, 17, 37, 4, 0)$ ，该攻击将声称的 186 位安全性降低到了大约 35 位。
效率：在作者的实现中，针对 128 位参数集的等效秘密密钥在不到 10 分钟内即可被恢复。
对比：如论文表 1 所示，该攻击在性能上大幅超越了以往的最优攻击（包括组合攻击和 MinRank 攻击）。

意义与主张
论文声称，对于 $\ell_1 = 0$ 或 $\ell_2 = 0$ 的特定参数族，所提议的 EGMC 构造无法提供后量子安全性。作者认为，如果不改变掩码构造，仅仅增加参数无法恢复安全性，因为代数求解步骤仍然是多项式时间的。

作者指出，潜在的修复方案需要保持 $\ell_1$ 和 $\ell_2$ 均为非零且足够大，以确保两个攻击方向中的最小值超过目标安全水平。然而，作者也提醒道，直接增加这些参数会直接增加公钥和密文的大小，且目前尚需研究这种修复方案是否仍能与其他基于码的方案保持竞争优势。论文结论认为，当前的 EGMC 参数是不安全的，且所提攻击同时提供了区分器和完整的密钥恢复机制。

这篇论文的重要发现

这篇论文实际上破解了什么

这篇论文排除了什么

他们有多确定？

类似论文