🔢 mathematics

On the Direct Construction of MDS and Near-MDS Matrices

本文提出了近最大距离可分（NMDS）矩阵的非递归与递归直接构造方法，利用广义范德蒙德矩阵构建了非递归最大距离可分（MDS）矩阵及对合 MDS/NMDS 矩阵，并证明了相关 NMDS 码的已知结论。

原作者： Kishan Chand Gupta, Sumit Kumar Pandey, Susanta Samanta

发布于 2026-04-10

📖 1 分钟阅读🧠 深度阅读

原作者： Kishan Chand Gupta, Sumit Kumar Pandey, Susanta Samanta

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

这篇论文主要是在解决一个密码学领域的“拼图”问题：如何更高效、更聪明地制造一种叫做MDS 矩阵和近 MDS 矩阵的数学工具。

为了让你轻松理解，我们可以把加密算法想象成一家超级安全的银行金库。

1. 核心角色：扩散层（Diffusion Layer）

在金库里，为了防止小偷（黑客）通过观察一点点线索就猜出密码，银行设计了一种特殊的“搅拌器”。

作用：当你把一把钥匙（明文）插进去，这个搅拌器会把钥匙的每一个齿痕都打散，均匀地混合到整个金库的每一个角落。
数学本质：这个“搅拌器”在数学上就是一个矩阵。
MDS 矩阵（完美搅拌器）：这是最顶级的搅拌器。它能把信息混合得完美无缺，任何一点输入的变化都会瞬间影响所有输出。这是目前最安全的标准，但制造起来很贵（计算复杂，耗电多）。
NMDS 矩阵（近完美搅拌器）：这是一种“性价比”极高的搅拌器。它的混合效果稍微差一点点（不是 100% 完美），但制造成本极低，速度快，特别适合用在智能卡、物联网设备等“轻量级”设备上。

2. 过去的难题：寻找 vs. 制造

以前，科学家想造出这些矩阵，主要有两种方法：

** exhaustive Search（ exhaustive 搜索/大海捞针）**：就像在沙滩上随机捡贝壳，直到捡到一个完美的。
- 缺点：沙滩（数学空间）太大了，对于大一点的矩阵，就算用超级计算机捡一辈子也捡不完。
Direct Construction（直接制造/按图纸生产）：就像有了图纸，直接按公式造出来。
- 现状：对于“完美搅拌器”（MDS），大家已经有很多图纸了。但是，对于“近完美搅拌器”（NMDS），尤其是那种可以递归使用（像俄罗斯套娃一样，用一个小零件反复折叠就能变大）的图纸，以前是空白的！没人知道怎么直接造出来。

3. 这篇论文的三大突破（新图纸）

这篇论文就像是一个天才建筑师，拿出了三套全新的建筑图纸：

突破一：填补了“递归 NMDS"的空白

比喻：以前大家只会造“一次性”的搅拌器，或者只会造“完美”的套娃。现在，作者发明了一种**“递归近完美搅拌器”**。
怎么做：他们利用了一种叫**“伴随矩阵”**（Companion Matrix）的数学结构。想象这是一种特殊的齿轮组，只要设定好齿轮的齿数（多项式的根），就能自动折叠出完美的混合效果。
意义：这是世界上第一次有人直接给出了这种递归 NMDS 矩阵的制造公式，不再需要大海捞针了。

突破二：引入了“广义范德蒙德矩阵”作为新工具

比喻：以前的图纸主要用“范德蒙德矩阵”（Vandermonde Matrix），这就像是用标准的乐高积木。但作者发现，如果去掉几块特定的积木（在数学上叫“广义”），或者重新排列积木的堆叠顺序，就能造出以前造不出来的形状。
怎么做：他们利用广义范德蒙德矩阵，通过巧妙地选择数字（就像选择不同颜色的积木），直接造出了非递归的 MDS 和 NMDS 矩阵。
意义：这大大扩展了工具箱，让造出来的矩阵更多样化。

突破三：发明了“自反”搅拌器（Involutory Matrices）

比喻：在加密时，你需要把信息“搅拌”进去；解密时，你需要把信息“还原”出来。通常，搅拌和还原需要两套不同的机器（两个不同的矩阵），这很占地方。
创新：作者造出了一种**“自反”矩阵**。这种矩阵有个神奇特性：搅拌和还原用的是同一套机器！ 你把它转个身，它就能把刚才搅乱的东西原样复原。
意义：这对硬件设计太重要了！意味着加密和解密可以共用一套电路，省空间、省电、速度快。这是世界上第一次直接造出了“自反的近完美搅拌器”。

4. 总结：这有什么用？

想象一下，你手里有一个智能门锁（轻量级设备），它的电池很小，芯片也很小。

以前：为了安全，它得用“完美搅拌器”，结果电池撑不住，或者芯片太贵。为了省钱，它只能用“次品”，安全性又不够。
现在：有了这篇论文的新图纸，工程师可以：
1. 直接造出递归的 NMDS 矩阵，用极少的电路实现复杂的混合。
2. 造出自反矩阵，加密解密共用一套电路，省了一半的硬件成本。

一句话总结：
这篇论文就像给密码学家提供了一套全新的、现成的“乐高说明书”，让他们能直接拼出既安全又省钱的“混合器”，特别是填补了“近完美”且“可递归”的拼图空白，让未来的物联网设备既能防盗，又不会把电池耗尽。

这是一份关于论文《On the Direct Construction of MDS and Near-MDS Matrices》（MDS 和近 MDS 矩阵的直接构造）的详细技术总结。

1. 研究背景与问题 (Problem)

在对称密钥密码学（如分组密码和哈希函数）的设计中，扩散层（Diffusion Layer） 至关重要，其目标是最大化内部依赖的扩散。

MDS 矩阵：具有最优分支数（Branch Number），能提供完美的扩散，是许多密码算法（如 AES）的首选。然而，构建大阶数 MDS 矩阵通常依赖穷举搜索，计算量巨大，难以扩展。
近 MDS (NMDS) 矩阵：具有次优分支数，扩散速度略慢于 MDS 矩阵，但在轻量级密码学中，它们能在安全性和实现效率（硬件成本、延迟）之间提供更好的平衡。
现有研究的不足：
1. 虽然文献中已有大量关于 MDS 矩阵直接构造（递归和非递归）的研究，但缺乏递归 NMDS 矩阵的直接构造方法。现有的 NMDS 构造多基于搜索或从特定编码推导，缺乏通用的代数构造框架。
2. 对于对合（Involutory） 矩阵（即 $M^2=I$ ，加密和解密使用同一矩阵，可节省硬件资源），现有的 NMDS 构造方法匮乏，尤其是缺乏直接的构造公式。
3. 文献中关于 NMDS 码的一些“常识性结果”（Folklore results）缺乏严格的证明。

2. 方法论 (Methodology)

本文提出了一套基于广义范德蒙德矩阵（Generalized Vandermonde Matrices） 和伴随矩阵（Companion Matrices） 的代数构造框架。

核心数学工具

广义范德蒙德矩阵 $V^\perp(x; I)$ ：
通过从标准范德蒙德矩阵的幂次集合中移除特定的指数集合 $I$ 来定义。利用其行列式性质（涉及初等对称多项式 $\sigma_d$ ），作者推导出了矩阵非奇异及子矩阵满秩的代数条件。
伴随矩阵与递归构造：
利用伴随矩阵 $C_g$ 的特征值分解性质（ $C_g = V D V^{-1}$ ），将递归 MDS/NMDS 矩阵的构造问题转化为对多项式根 $\lambda_i$ 的选择问题。
对合性构造：
在特征为 2 的有限域 $\mathbb{F}_{2^r}$ 上，通过设定两组广义范德蒙德矩阵元素之间的线性关系（ $y_i = l + x_i$ ），推导出构造对合矩阵的条件。

构造策略

递归构造：
- 通过选择多项式 $g(x)$ 的根，使得生成的矩阵 $C_g^m$ 满足 MDS 或 NMDS 的线性无关/相关条件。
- 对于 NMDS，故意引入特定的线性依赖（如根的和为零），同时保证其他子矩阵满秩。
非递归构造：
- 利用两个广义范德蒙德矩阵 $V_1$ 和 $V_2$ 构造矩阵 $A = V_1^{-1} V_2$ 。
- 通过控制 $V_1$ 和 $V_2$ 的元素集合 $x$ 和 $y$ 的代数性质（如子集和不为零或为零），确保 $A$ 及其子矩阵满足 MDS 或 NMDS 的秩条件。
对合性：
- 在偶数阶矩阵和 $\mathbb{F}_{2^r}$ 域上，通过特定的元素映射关系，证明 $V_1^{-1} V_2$ 是对合矩阵。

3. 主要贡献 (Key Contributions)

递归 NMDS 矩阵的直接构造：
- 填补了文献空白，首次提出了基于伴随矩阵的递归 NMDS 矩阵直接构造方法（定理 10 和引理 11）。
- 提出了新的递归 MDS 矩阵构造方法（定理 11）。
基于广义范德蒙德矩阵的非递归构造：
- 利用广义范德蒙德矩阵 $V^\perp(x; I)$ （其中 $I=\{1\}, \{n-1\}, \{1, n\}$ ），提出了多种构造非递归 MDS 和 NMDS 矩阵的新方法（定理 12, 13, 15, 16, 17）。
- 揭示了通过移除特定幂次（集合 $I$ ）可以改变行列式结构，从而满足 NMDS 的特定秩条件。
对合（Involutory）矩阵的构造：
- 提出了构造对合 MDS 矩阵的新方法（推论 7）。
- 首次提出了有限域上对合 NMDS 矩阵的直接构造方法（推论 8），无需依赖穷举搜索。
理论证明：
- 为文献中广泛引用但缺乏证明的关于 NMDS 码的几个“常识性结果”提供了严格的数学证明（如定理 4 的证明，以及 NMDS 码与其对偶码的关系等）。

4. 研究结果 (Results)

理论验证：通过一系列定理和引理，严格证明了在特定代数条件下（如根的选取、子集和条件），构造出的矩阵确实满足 MDS 或 NMDS 的定义。
实例演示：
- 在 $\mathbb{F}_{2^4}$ 和 $\mathbb{F}_{2^8}$ 等有限域上提供了具体的构造实例（如例 4-16）。
- 展示了如何生成具体的 $4 \times 4$ 甚至更大阶数的 MDS/NMDS 矩阵，包括对合矩阵。
- 验证了构造出的矩阵满足所需的分支数和线性无关性条件。
对比分析：
- 表 1 详细对比了本文提出的方法与现有文献（如 Cauchy 矩阵、标准 Vandermonde 矩阵、BCH 码等构造法）。
- 本文方法在递归 NMDS和对合 NMDS领域是首创，且提供了更广泛的代数构造空间。

5. 意义与影响 (Significance)

填补理论空白：解决了长期存在的“缺乏递归 NMDS 直接构造”的问题，为轻量级密码学扩散层的设计提供了新的理论工具。
扩展设计空间：通过引入广义范德蒙德矩阵和特定的代数约束，突破了传统 Cauchy 或标准 Vandermonde 构造的局限，提供了更多样化的矩阵生成路径。
提升实现效率：
- 对合性：构造出的对合矩阵使得加密和解密可以使用相同的硬件逻辑，显著降低了硬件面积和成本，特别适合资源受限的 IoT 设备。
- 直接构造 vs. 搜索：相比于依赖穷举搜索（仅适用于小阶数），本文的直接构造方法可以扩展到更大的矩阵阶数，具有更好的可扩展性。
未来方向：论文指出，这些新发现的矩阵类为后续研究提供了基础，未来可结合全局优化启发式算法，进一步评估这些矩阵在具体硬件实现中的面积、延迟和功耗指标，以推动其在轻量级密码原语中的实际应用。

总结：该论文通过深入的代数分析，建立了一套系统的直接构造框架，成功生成了递归和非递归的 MDS 及 NMDS 矩阵，特别是首次实现了对合 NMDS 矩阵的直接构造，为现代密码学扩散层的设计提供了重要的理论支撑和实用工具。