2025-11-10T02:59:44.540641

A Characterization of Semi-Involutory MDS Matrices

Chatterjee, Laha
In symmetric cryptography, maximum distance separable (MDS) matrices with computationally simple inverses have wide applications. Many block ciphers like AES, SQUARE, SHARK, and hash functions like PHOTON use an MDS matrix in the diffusion layer. In this article, we first characterize all $3 \times 3$ irreducible semi-involutory matrices over the finite field of characteristic $2$. Using this matrix characterization, we provide a necessary and sufficient condition to construct MDS semi-involutory matrices using only their diagonal entries and the entries of an associated diagonal matrix. Finally, we count the number of $3 \times 3$ semi-involutory MDS matrices over any finite field of characteristic $2$.
academic

A Characterization of Semi-Involutory MDS Matrices

基本信息

  • 论文ID: 2406.12842
  • 标题: A Characterization of Semi-Involutory MDS Matrices
  • 作者: Tapas Chatterjee (Indian Institute of Technology Ropar), Ayantika Laha (Indian Institute of Technology Ropar)
  • 分类: cs.CR (Cryptography and Security)
  • 发表时间: 2025年1月1日 (v2版本)
  • 论文链接: https://arxiv.org/abs/2406.12842

摘要

在对称密码学中，具有计算简单逆矩阵的最大距离可分离(MDS)矩阵有着广泛的应用。许多分组密码如AES、SQUARE、SHARK以及哈希函数如PHOTON都在扩散层中使用MDS矩阵。本文首先刻画了特征为2的有限域上所有3×3不可约半对合矩阵。基于这种矩阵刻画，我们提供了仅使用对角线元素和相关对角矩阵元素构造MDS半对合矩阵的充分必要条件。最后，我们计算了特征为2的任意有限域上3×3半对合MDS矩阵的数量。

研究背景与动机

问题背景

  1. 扩散层的重要性: 在对称密码学中，Shannon提出的"混淆与扩散"概念是密码设计的基础。扩散层负责隐藏密文与明文之间的关系，而MDS矩阵由于其最大分支数可以提供完美扩散。
  2. 计算效率需求: 在轻量级密码学应用中，不仅需要MDS矩阵提供安全性，还需要其逆矩阵具有高效的实现。对合矩阵(A² = I)因为其逆矩阵就是自身而备受关注。
  3. 现有方法的局限性:
    • 对合MDS矩阵的搜索空间相对有限
    • 某些尺寸的对合循环矩阵不存在
    • 需要更广泛的矩阵类来扩展设计选择

研究动机

本文引入半对合矩阵作为对合矩阵的推广，其定义为存在非奇异对角矩阵D₁和D₂使得M⁻¹ = D₁MD₂。这种推广显著扩展了可用于密码设计的矩阵类别。

核心贡献

  1. 理论刻画: 完全刻画了特征为2的有限域上所有3×3不可约半对合矩阵的结构
  2. 构造方法: 提供了仅使用6个参数(3个对角元素+3个相关对角矩阵元素)构造3×3半对合MDS矩阵的充分必要条件
  3. 计数结果: 精确计算了F₂ᵐ上3×3半对合MDS矩阵的数量为(2ᵐ-1)⁵(2ᵐ-2)(2ᵐ-4)
  4. 推广已有结果: 将Güzel等人关于对合MDS矩阵的结果推广到更大的半对合矩阵类

方法详解

任务定义

研究特征为2的有限域F₂ᵐ上3×3矩阵A，要求：

  • 半对合性: 存在非奇异对角矩阵D使得ADA为对角矩阵
  • MDS性质: A的所有方形子矩阵都非奇异
  • 不可约性: A不能通过置换相似化为约化形式

核心定理

定理4.1 (结构刻画)

设A为3×3不可约半对合矩阵，关联对角矩阵为D = diag(d₁,d₂,d₃)，则非对角元素可表示为：

  • a₁₂ = (a₁₁d₁ + a₃₃d₃)d₂⁻¹x
  • a₁₃ = (a₁₁d₁ + a₂₂d₂)d₃⁻¹xy
  • a₂₁ = (a₂₂d₂ + a₃₃d₃)d₁⁻¹x⁻¹
  • a₂₃ = (a₂₂d₂ + a₁₁d₁)d₃⁻¹y
  • a₃₁ = (a₃₃d₃ + a₂₂d₂)d₁⁻¹(xy)⁻¹
  • a₃₂ = (a₃₃d₃ + a₁₁d₁)d₂⁻¹y⁻¹

其中x,y ∈ F₂ᵐ*为非零元素。

定理4.5 (MDS充要条件)

上述结构的矩阵A为半对合MDS矩阵当且仅当：

  • a₁₁d₁ + a₂₂d₂ ≠ 0
  • a₁₁d₁ + a₃₃d₃ ≠ 0
  • a₂₂d₂ + a₃₃d₃ ≠ 0
  • a₁₁d₁ + a₂₂d₂ + a₃₃d₃ ≠ 0

技术创新点

  1. 统一框架: 将对合矩阵作为半对合矩阵的特例，提供了统一的分析框架
  2. 参数化构造: 通过8个参数完全刻画3×3半对合MDS矩阵，大大简化了搜索空间
  3. 计数技术: 使用容斥原理精确计算满足条件的参数组合数量

实验设置

理论验证

论文主要为理论工作，通过具体例子验证理论结果：

例子4.6: 在F₂₄上构造半对合MDS矩阵

  • 生成多项式: x⁴ + x³ + 1
  • 参数选择: a₁₁=1, a₂₂=α, a₃₃=α², d₁=α, d₂=α, d₃=α³+1, x=1, y=α
  • 验证所有MDS条件均满足

计数验证

通过具体计算验证计数公式：

  • F₂₂: 0个半对合MDS矩阵
  • F₂₃: 403,368个半对合MDS矩阵
  • F₂₄: 127,575,000个半对合MDS矩阵

实验结果

主要结果

  1. 结构完整性: 成功刻画了所有3×3半对合矩阵的结构，证明了其可以用8个参数完全确定
  2. MDS判定: 提供了判定半对合矩阵何时具有MDS性质的简洁条件
  3. 数量增长: 相比对合MDS矩阵，半对合MDS矩阵数量显著增加：
    • F₂₃上对合MDS矩阵: 1,176个
    • F₂₃上半对合MDS矩阵: 403,368个 (增长约343倍)

理论发现

  1. 推广性: 半对合性质真正推广了对合性质，存在半对合但非对合的MDS矩阵
  2. 计算优势: 半对合MDS矩阵的逆矩阵仍可通过简单的对角矩阵乘法获得，保持了计算效率
  3. 存在性: 在F₂₂上不存在满足条件的半对合MDS矩阵，但在F₂ᵐ (m≥3)上存在大量此类矩阵

相关工作

历史发展

  1. 对合矩阵研究: Youssef等人(2007)首次在密码学中引入对合线性变换
  2. MDS构造方法: Gupta和Ray(2013)提供了多种MDS矩阵构造方法
  3. 循环矩阵限制: Gupta等人证明了对合循环矩阵的不存在性
  4. 半对合概念: Cheon等人(2021)引入半对合矩阵概念

本文贡献

相比现有工作，本文：

  • 将半对合概念首次应用于MDS矩阵构造
  • 提供了比对合矩阵更大的设计空间
  • 给出了精确的计数结果

结论与讨论

主要结论

  1. 完全刻画了3×3半对合矩阵的代数结构
  2. 建立了半对合性与MDS性质之间的联系
  3. 证明了半对合MDS矩阵在密码设计中的实用价值

局限性

  1. 维数限制: 当前结果仅适用于3×3矩阵
  2. 特征限制: 理论主要针对特征2的有限域
  3. 不可约性: 要求矩阵具有不可约性质

未来方向

  1. 推广到更高维矩阵(特别是偶数阶或2的幂次阶)
  2. 研究其他特征有限域上的情况
  3. 探索半对合矩阵在实际密码系统中的应用

深度评价

优点

  1. 理论完整性: 提供了3×3半对合MDS矩阵的完整刻画，理论结果严谨
  2. 实用价值: 为密码设计提供了新的工具，扩展了设计空间
  3. 计算效率: 保持了逆矩阵计算的简单性，适合轻量级应用
  4. 精确计数: 给出了精确的存在数量，有助于随机选择

不足

  1. 维数限制: 仅考虑3×3情况，更高维的推广仍是开放问题
  2. 构造复杂性: 虽然给出了参数化形式，但实际构造仍需满足多个约束条件
  3. 应用验证: 缺乏在实际密码系统中的安全性分析

影响力

  1. 理论贡献: 为有限域上矩阵理论提供了新的见解
  2. 密码应用: 为轻量级密码设计提供了新的候选矩阵
  3. 方法创新: 计数方法可推广到其他类似问题

适用场景

  1. 轻量级密码: 适用于资源受限环境下的分组密码设计
  2. 哈希函数: 可用于需要高效扩散层的哈希函数构造
  3. 理论研究: 为进一步研究更高维情况提供了基础

参考文献

论文引用了25篇相关文献，主要包括：

  • Shannon的密码理论基础工作
  • AES等经典密码算法
  • MDS矩阵构造的重要理论结果
  • 半对合矩阵的最新研究进展

该工作在现有理论基础上取得了实质性进展，为半对合MDS矩阵的理论和应用奠定了坚实基础。