New Insights into Involutory and Orthogonal MDS Matrices

技术摘要：关于对合（Involutory）与正交（Orthogonal）MDS 矩阵的新见解

问题陈述
最大距离可分（MDS）矩阵由于其最优的分支数，在分组密码和哈希函数的扩散层中具有基础性作用。虽然目前已有大量关于构建高效 MDS 候选矩阵的文献，但特定的结构属性——即对合（自逆）和正交（转置逆）属性——对于降低实现成本（允许加密和解密使用相同或近乎相同的电路）而言是非常理想的。最近，这些概念被推广为“半对合”（semi-involutory）和“半正交”（semi-orthogonal）矩阵。然而，现有的研究主要集中在提出新的构造方法或优化实现指标上。目前仍缺乏对于这些广义变体（半对合/半正交）与其传统对应物（对合/正交）之间结构互连性的系统性理解，特别是在有限域 $\mathbb{F}_{2^m}$ 上的计数问题。

方法论
作者采用结构分析法而非提出新的矩阵构造。核心方法论依赖于将 $\mathbb{F}_{2^m}^*$ 上的非奇异矩阵唯一分解为形式 $M = D_1 M_1 D_2$，其中 $D_1$ 和 $D_2$ 是非奇异对角矩阵，$M_1$ 是具有特定规范形式（第一行和第一列由 1 组成）的“代表矩阵”。

关键方法步骤包括：

1. 建立互连关系： 本文证明了当应用对角缩放 $D_1 M_1 D_2$ 时，对合、半对合、正交或半正交的属性是如何以可预测的方式被保持或转换的。
2. 推导计数关系： 通过分析使矩阵 $M$ 满足特定属性所需的对 $D_1$ 和 $D_2$ 的约束，作者推导出了广义矩阵与其传统对应物计数之间的双向关系。
3. 结构特征化： 作者推导了 $\mathbb{F}_{2^m}$ 上任意阶 $n$ 正交矩阵的一般代数结构，并将其特化至 $n=3$ 和 $n=4$ 的情况。
4. 枚举： 利用已知的对合 MDS 矩阵枚举结果以及推导出的结构关系，作者计算了特定阶数和域大小下的半对合及半正交 MDS 矩阵的精确数量。

主要贡献与结果

• 结构互连： 本文建立了半对合与对合矩阵之间、以及半正交与正交矩阵之间非平凡的关系。具体而言，证明了 $n \times n$ 对合 MDS 矩阵的数量是形式为 $M_1$ 的半对合 MDS 矩阵数量的 $(2^m - 1)^{n-1}$ 倍。对于半正交和正交矩阵，也证明了类似的对应关系。
• 3×3 矩阵枚举：
  • 正交 MDS： 作者推导出 $\mathbb{F}_{2^m}$ 上 $3 \times 3$ 正交 MDS 矩阵数量的显式公式为 $(2^m - 2)(2^m - 3)(2^m - 4)$。
  • 半正交 MDS： 利用结构联系，他们推导出 $3 \times 3$ 半正交 MDS 矩阵的计数为 $(2^m - 1)^5(2^m - 2)(2^m - 3)(2^m - 4)$。
  • 半对合 MDS： 本文提供了 $3 \times 3$ 半对合 MDS 矩阵计数的直接推导，证实了公式 $(2^m - 1)^5(2^m - 2)(2^m - 4)$。这作为文献中先前证明的一种替代方案。
• 属性交集： 作者表征了既是半对合又是半正交的矩阵。他们证明了对于 $3 \times 3$ 矩阵，任何形式为 $M_1$ 的半对合矩阵必然是对称的，这意味着同时具备这两种属性的矩阵数量与半对合矩阵的数量相同。
• 4×4 矩阵枚举： 研究扩展到了 $4 \times 4$ 矩阵。作者计算了当 $m = 3, \dots, 8$ 时半对合 MDS 矩阵的数量，以及当 $m=3, 4$ 时正交/半正交矩阵的数量。他们还基于 d-XOR 门计数识别了 4 阶轻量级正交 MDS 矩阵，发现 $\mathbb{F}_{2^3}$ 上有 64 个，$\mathbb{F}_{2^4}$ 上有 72 个最优计数。
• 一般结构： 推导了 $\mathbb{F}_{2^m}$ 上 $n \times n$ 正交矩阵的一般形式，将最后一行和最后一列表示为剩余子矩阵元素及特定求和约束的函数。

意义与主张
本文声称提供了一个统一的框架，用于理解具有特定结构约束的 MDS 矩阵的枚举。通过将重点从构造转向结构关系，作者表明，广义变体（半对合/半正交）的计数可以直接从其传统对应物的计数中推导出来。

作者指出，其工作提供了：

1. 替代推导： 与现有的综合证明相比，为 $3 \times 3$ 半对合和半正交 MDS 矩阵的计数公式提供了更直接、更简洁的推导。
2. 新的枚举数据： 给出了 $3 \times 3$ 正交 MDS 矩阵的显式计数（此前在文献中尚未确立）以及更大有限域下 $4 \times 4$ 矩阵的扩展计数。
3. 理论洞察： 证明了对于 $3 \times 3$ 矩阵，半对合与半正交属性的交集与半对合矩阵集一致，这一属性对于更高阶（如 $n \ge 4$）并不一定成立。

论文总结道，这些互连关系提供了一种系统的方法，用于确定满足附加结构约束的 MDS 矩阵的数量，从而整合了若干个代数约束下的 $3 \times 3$ 和 $4 \times 4$ MDS 类别的显式枚举公式。