New Insights into Involutory and Orthogonal MDS Matrices

• URL: http://arxiv.org/abs/2510.05766v1
• Date: Tue, 07 Oct 2025 10:35:20 GMT
• Title: New Insights into Involutory and Orthogonal MDS Matrices
• Authors: Yogesh Kumar, Susanta Samanta, Atul Gaur,
• Abstract summary: MDS matrices play a critical role in the design of diffusion layers for block ciphers and hash functions.<n>We show nontrivial interconnections between semi-involutory and involutory matrices.<n>We present explicit formulas for counting $3 times 3$ semi-involutory MDS matrices and semi-orthogonal MDS matrices.
• Score: 1.9947454698470526
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: MDS matrices play a critical role in the design of diffusion layers for block ciphers and hash functions due to their optimal branch number. Involutory and orthogonal MDS matrices offer additional benefits by allowing identical or nearly identical circuitry for both encryption and decryption, leading to equivalent implementation costs for both processes. These properties have been further generalized through the notions of semi-involutory and semi-orthogonal matrices. Specifically, we establish nontrivial interconnections between semi-involutory and involutory matrices, as well as between semi-orthogonal and orthogonal matrices. Exploiting these relationships, we show that the number of semi-involutory MDS matrices can be directly derived from the number of involutory MDS matrices, and vice versa. A similar correspondence holds for semi-orthogonal and orthogonal MDS matrices. We also examine the intersection of these classes and show that the number of $3 \times 3$ MDS matrices that are both semi-involutory and semi-orthogonal coincides with the number of semi-involutory MDS matrices over $\mathbb{F}_{2^m}$. Furthermore, we derive the general structure of orthogonal matrices of arbitrary order $n$ over $\mathbb{F}_{2^m}$. Based on this generic form, we provide a closed-form expression for enumerating all $3 \times 3$ orthogonal MDS matrices over $\mathbb{F}_{2^m}$. Finally, leveraging the aforementioned interconnections, we present explicit formulas for counting $3 \times 3$ semi-involutory MDS matrices and semi-orthogonal MDS matrices.

Related papers

• High-Rank Irreducible Cartesian Tensor Decomposition and Bases of Equivariant Spaces [48.465738895704455]
  We construct path matrices for decomposition of Cartesian tensors up to rank $n=9$ with reduced and affordable complexity.<n>Our method avoids the RREF algorithm and maintains a fully analytical derivation of each ICT decomposition matrix.<n>We extend our result to the arbitrary tensor product and direct sum spaces, enabling free design between different spaces while keeping symmetry.
  arXiv  Detail & Related papers  (2024-12-24T08:25:38Z)
• Understanding Matrix Function Normalizations in Covariance Pooling through the Lens of Riemannian Geometry [63.694184882697435]
  Global Covariance Pooling (GCP) has been demonstrated to improve the performance of Deep Neural Networks (DNNs) by exploiting second-order statistics of high-level representations.<n>This paper provides a comprehensive and unified understanding of the matrix logarithm and power from a Riemannian geometry perspective.
  arXiv  Detail & Related papers  (2024-07-15T07:11:44Z)
• A note on MDS Property of Circulant Matrices [3.069335774032178]
  In $2014$, Gupta and Ray proved that the circulant involutory matrices over the finite field $mathbbF_2m$ can not be maximum distance separable (MDS) This article delves into circulant matrices possessing these characteristics over the finite field $mathbbF_2m$.
  arXiv  Detail & Related papers  (2024-06-22T16:00:00Z)
• On MDS Property of g-Circulant Matrices [3.069335774032178]
  We first discuss $g$-circulant matrices with involutory and MDS properties. We then delve into $g$-circulant semi-involutory and semi-orthogonal matrices with entries from finite fields.
  arXiv  Detail & Related papers  (2024-06-22T15:18:31Z)
• A Characterization of Semi-Involutory MDS Matrices [3.069335774032178]
  In symmetric cryptography, maximum distance separable (MDS) matrices with computationally simple inverses have wide applications.<n>Many block ciphers like AES, SQUARE, SHARK, and hash functions like PHOTON use an MDS matrix in the diffusion layer.
  arXiv  Detail & Related papers  (2024-06-18T17:57:46Z)
• A Systematic Construction Approach for All $4\times 4$ Involutory MDS Matrices [1.3332839594069594]
  We present several characterizations of involutory MDS matrices of even order. We propose a technique to systematically construct all $4 times 4$ involutory MDS matrices over a finite field.
  arXiv  Detail & Related papers  (2024-04-12T05:37:42Z)
• On the Counting of Involutory MDS Matrices [0.0]
  This paper enumerates Hadamard MDS and involutory Hadamard MDS matrices of order $4$ within the field $mathbbF_2r$. It also derives the count of Hadamard-MDS (NMDS) and involutory Hadamard NMDS matrices, each with exactly one zero in each row, of order $4$ over $mathbbF_2r$.
  arXiv  Detail & Related papers  (2023-09-29T18:57:00Z)
• Deep Learning Symmetries and Their Lie Groups, Algebras, and Subalgebras from First Principles [55.41644538483948]
  We design a deep-learning algorithm for the discovery and identification of the continuous group of symmetries present in a labeled dataset. We use fully connected neural networks to model the transformations symmetry and the corresponding generators. Our study also opens the door for using a machine learning approach in the mathematical study of Lie groups and their properties.
  arXiv  Detail & Related papers  (2023-01-13T16:25:25Z)
• Semi-Supervised Subspace Clustering via Tensor Low-Rank Representation [64.49871502193477]
  We propose a novel semi-supervised subspace clustering method, which is able to simultaneously augment the initial supervisory information and construct a discriminative affinity matrix. Comprehensive experimental results on six commonly-used benchmark datasets demonstrate the superiority of our method over state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-05-21T01:47:17Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  We introduce a generalization of the popular Nystr"om method to the indefinite setting. Our algorithm can be applied to any similarity matrix and runs in sublinear time in the size of the matrix. We show that our method, along with a simple variant of CUR decomposition, performs very well in approximating a variety of similarity matrices.
  arXiv  Detail & Related papers  (2021-12-17T17:04:34Z)
• Non-PSD Matrix Sketching with Applications to Regression and Optimization [56.730993511802865]
  We present dimensionality reduction methods for non-PSD and square-roots" matrices. We show how these techniques can be used for multiple downstream tasks.
  arXiv  Detail & Related papers  (2021-06-16T04:07:48Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.