🔢 mathematics

MDS matrices from skew polynomials with automorphisms and derivations

本文提出了一种利用带有自同构和导数的斜多项式环来构造最大距离可分（MDS）矩阵的新方法，引入了 $\delta_\theta$ -循环矩阵，并推导了使其成为对合矩阵及MDS矩阵的充分必要条件，同时提供了改进以往拟对合结果的拟递归MDS矩阵。

原作者： Atif Ahmad Khan, Shakir Ali, Elif Segah Oztas, Abhishek Kesarwani

发布于 2026-02-03

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Atif Ahmad Khan, Shakir Ali, Elif Segah Oztas, Abhishek Kesarwani

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

大局观：构建更好的数字锁

想象你正在建造一个数字保险箱。为了确保安全，你需要两个核心要素：

混淆（Confusion）： 让你的密码与锁定的保险箱之间的关系看起来像一团乱麻。
扩散（Diffusion）： 确保即使你只改变了密码中极其微小的一点，整个保险箱的状态也会发生彻底的变化。

在密码学（数字安全）领域，MDS 矩阵是用于创造这种“扩散”效果的特殊工具。可以将 MDS 矩阵想象成一个超级搅拌器。如果你把一滴红墨水（一段数据）倒入一桶清水（矩阵）中，一个完美的 MDS 矩阵能确保红色均匀地扩散到桶里的每一滴水中。如果搅拌得不完美，有些地方仍会保持清澈，黑客就能通过这些模式破解锁具。

这篇论文的研究内容是利用一种特殊的数学“厨房”——斜多项式环（Skew Polynomial Rings），来发明新的、更好的搅拌工具。

原料：对标准数学的“扭转”

通常情况下，数学家使用标准的多项式环（例如 $x^2 + 2x + 1$ ）来构建这些搅拌工具。但作者决定使用一种被称为**斜多项式（Skew Polynomials）**的“扭转”版本。

要理解这种“扭转”，想象一个标准的食谱，其中混合食材的顺序是固定的。但在本文的“扭转”厨房里，由于两条特殊规则的存在，顺序变得更加重要：

自同构 ( $\theta$ )： 想象一位神奇的厨师，他在你混合食材之前会改变食材的味道。如果你有一个苹果，厨师可能会在放入碗中之前把它变成一个梨。
导数 ( $\delta$ )： 想象第二条规则：在混合过程中，会根据食材的情况加入一点“额外的酱汁”。

作者结合了这两条规则，创造出了一种新型的搅拌工具，称为 $\delta\theta$ -循环矩阵（ $\delta\theta$ -circulant matrix）。

类比： 将标准的“循环”矩阵想象成一条传送带，上面的图案只是向右滑动。而这种新的 $\delta\theta$ -循环 矩阵则像是一条传送带，当图案滑动时，物品还会被“神奇厨师”进行变换，并溅上一些“额外的酱汁”。

第一项发现：新的搅拌模式

作者展示了通过使用这些扭转规则，他们可以构建出以前无法制造的新型混合矩阵。

目标： 他们想要制造既是 MDS（完美的搅拌器）又是 对合（Involutory）（自反/自反转）的矩阵。
“自反”类比： 想象一面魔镜。如果你看它，你看到的是你自己；如果你再次看它，你看到的依然是自己。在数学中，“对合”矩阵是一种工具，如果你用它来打乱数据，然后再使用它一次，数据就会恢复原状。这在加密中非常有用，因为它节省了时间和能量；你不需要另外准备一个“解密”工具。

论文证明了，通过精心选择“厨师”和“酱汁”，他们可以创造出这些完美的自反搅拌器。这意义重大，因为在旧有的“标准”厨房里，制造这类特定的完美搅拌器是非常困难（有时甚至是无法实现）的。

第二项发现：“拟递归”机器

论文的第二部分关注一种不同类型的搅拌工具，称为拟递归 MDS 矩阵（Quasi Recursive MDS matrices）。

类比： 想象一台机器，它先对一个形状进行冲压，然后对结果再次进行冲压，如此循环往复。
创新点： 作者制造了一台机器，其“冲压”过程极其高效，以至于如果你运行该机器特定次数，最终结果不仅是一个优秀的搅拌器，而且是一个完美的、自反的搅拌器。

此前，其他研究人员曾制造过“几乎”是自反的机器（称为拟对合/quasi-involutory）。本文的作者改进了设计，使该机器成为了严格自反的。这就像是将汽车引擎从“几乎能达到每加仑 50 英里”升级到了“精准达到每加仑 50 英里”。这是一种在效率上的严格提升。

他们是如何做到的：“哈达玛（Hadamard）”技巧

在接近尾声的部分，论文介绍了一个被称为**哈达玛积（Hadamard product）**的巧妙技巧。

类比： 想象你有一个完美的蛋糕食谱。作者找到了一种方法，可以将那份食谱中的每一种食材单独地“喷洒”上一层特殊的香料。
结果： 他们证明了，如果你拿一个已知的优秀搅拌配方，并应用这种“香料”（哈达玛积），你就能瞬间得到许多种全新的、同样完美的搅拌配方。这为工程师提供了一个巨大的工具箱供其选择，而不是仅限于一两个选项。

总结他们的研究主张

新工具： 他们利用扭转的数学框架，创造了一类新的混合矩阵（ $\delta\theta$ -循环矩阵）。
自反性： 他们证明了这些新工具可以是“自反的”（involutory），这使得加密过程更快、成本更低。
优于以往： 他们制造“拟递归”矩阵的方法产生了严格自反的结果，改进了以往仅能实现“几乎”自反的方法。
倍增选择： 他们展示了如何通过特定的数学运算（哈达玛积），从一个优秀的范例生成许多个有效的矩阵。

他们并未声称：
该论文并未声称构建了某种具体的加密软件，也未声称这些工具目前已用于商业产品。这是一篇理论数学论文，它提供了这些高效工具存在的蓝图和证明。至于如何构建具体的安全系统，他们将其留作未来的研究课题。

技术摘要：基于自同构与导数的斜多项式的 MDS 矩阵

问题陈述
最大距离可分（MDS）矩阵是设计对称密钥密码学中扩散层的基础，能够提供针对差分和线性攻击的最佳抵抗能力。虽然循环矩阵和递归矩阵因其高效的代数描述和实现特性而得到广泛研究，但现有的构造往往面临局限性。具体而言，经典循环矩阵在阶数为偶数时，无法同时满足 MDS 性质和对合（involutory，即自逆）性质，而对合性质对于降低密码原语的实现成本至关重要。以往利用斜多项式环中的自同构进行的推广（ $\theta$ -循环矩阵）虽然解决了其中一些问题，但通常仍局限于特定的有限域，或仅产生拟对合（quasi-involutory）矩阵。此外，通过将导数引入这些代数结构以进一步泛化可构造 MDS 矩阵的类别，尚未得到充分探索。

方法论
作者在斜多项式环 $F_q[X; \theta, \delta]$ 的框架下开发了其构造，其中 $F_q$ 是一个有限域， $\theta$ 是 $F_q$ 的一个自同构， $\delta$ 是一个 $\theta$ -导数。该非交换环中的乘法定义为规则 $Xa = \theta(a)X + \delta(a)$ 。

本文通过以下方法论步骤进行：

定义 $\delta\theta$ -循环矩阵： 作者引入了一类新的结构化矩阵，称为 $\delta\theta$ -循环矩阵，通过引入 $\theta$ -导数 $\delta$ ，它们泛化了经典循环矩阵和 $\theta$ -循环矩阵。这些矩阵的结构通过其与商环 $F_q[X; \theta, \delta] / \langle X^m - 1 \rangle$ 上线性变换的关联来进行分析。
代数特征化： 推导了使这些矩阵满足 MDS 性质和对合性质（ $A^2 = I$ ）的充要条件。这涉及分析斜环中多项式的权重以及生成多项式与所得矩阵之间的关系。
拟递归构造： 研究扩展到了准递归 MDS 矩阵，这类矩阵是通过涉及自同构和导数幂次的特定矩阵乘积定义的。作者重点研究了与单斜多项式相关的伴随矩阵。
Hadamard 积应用： 本文利用多项式的 Hadamard 积，从现有的 MDS 矩阵中生成新的 MDS 家族，并在特定条件下保持 MDS 性质。

核心贡献与结果

$\delta\theta$ -循环矩阵：
- 本文定义了 $\delta\theta$ -循环矩阵，并建立了这些矩阵与斜多项式环中线性变换之间的对应关系。
- 定理 2 提供了 $\delta\theta$ -循环矩阵为 MDS 的充要条件：对于任何非零多项式 $Q_1(X)$ ，其权重与 $Q_1(X)h(X) \pmod{X^m-1}$ 的权重之和必须至少为 $m+1$ 。
- 定理 3 建立了 $\delta\theta$ -循环矩阵为对合矩阵的条件，将其与生成多项式及其在斜环中的逆联系起来。
- 作者指出，虽然 $\theta$ -循环矩阵（其中 $\delta=0$ ）可以产生偶数阶的对合 MDS 矩阵，但引入 $\delta$ 扩大了可构造矩阵的类别。
拟递归对合 MDS 矩阵：
- 一项核心贡献是构造了严格对合的拟递归 MDS 矩阵（而非仅仅是拟对合）。
- 定理 5 表明，对于特定的自同构选择 $\theta(a) = a^{q^2}$ 和生成 MDS 码的多项式 $g(X)$ ，所得的拟递归矩阵 $N_g$ 满足 $N_g^2 = I_m$ 。这相对于以往的研究结果（例如 Cauchois 等人 [15]）是一个显著的改进，因为后者产生的仅是受限于特定域类的拟对合矩阵。
- 定理 6 将递归 MDS 矩阵的判别准则扩展到拟递归设置中，将 MDS 性质与生成多项式右倍数的权重联系起来。
新矩阵的生成：
- 定理 8 表明，如果多项式 $g(X)$ 生成一个拟递归 MDS 矩阵，那么其 Hadamard 幂 $(g(X))^{\diamond 2t}$ 也会生成一个拟递归 MDS 矩阵。这允许从单个种子多项式生成多个新的 MDS 矩阵。
- 定理 7 确立了用于生成对合 MDS 矩阵的倒数多项式同样会生成对合 MDS 矩阵。

意义与主张
本文声称其主要意义在于通过引入 $\theta$ -导数实现了现有 MDS 矩阵构造的泛化。具体而言：

它引入了 $\delta\theta$ -循环矩阵，这是一个比 $\theta$ -循环矩阵更广泛的类别，为循环结构和递归结构提供了一个统一的代数环境。
它提供了一种构造偶数阶对合拟递归 MDS 矩阵的方法，解决了先前文献中的局限性，即此类矩阵在经典设置中不存在，或者在斜设置中仅为拟对合。这对于密码学效率具有重要意义，因为对合矩阵消除了对独立逆实现的需要。
该工作提供了 MDS 性质和对合性质的显式判别准则，便于系统地构造此类矩阵。

作者承认，对 MDS $\delta\theta$ -循环矩阵的完整特征化仍是一个开放性问题，特别是当参数 $\beta$ （定义导数）不在自同构的固定域内时。他们还提出了这些矩阵是否具有正交性质的问题，作为未来的研究方向。