A Systematic Construction Approach for All $4\times 4$ Involutory MDS Matrices

• URL: http://arxiv.org/abs/2404.08250v2
• Date: Mon, 17 Jun 2024 15:41:08 GMT
• Title: A Systematic Construction Approach for All $4\times 4$ Involutory MDS Matrices
• Authors: Yogesh Kumar, P. R. Mishra, Susanta Samanta, Atul Gaur,
• Abstract summary: 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.
• Score: 1.3332839594069594
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Maximum distance separable (MDS) matrices play a crucial role not only in coding theory but also in the design of block ciphers and hash functions. Of particular interest are involutory MDS matrices, which facilitate the use of a single circuit for both encryption and decryption in hardware implementations. In this article, we present several characterizations of involutory MDS matrices of even order. Additionally, we introduce a new matrix form for obtaining all involutory MDS matrices of even order and compare it with other matrix forms available in the literature. We then propose a technique to systematically construct all $4 \times 4$ involutory MDS matrices over a finite field $\mathbb{F}_{2^m}$. This method significantly reduces the search space by focusing on involutory MDS class representative matrices, leading to the generation of all such matrices within a substantially smaller set compared to considering all $4 \times 4$ involutory matrices. Specifically, our approach involves searching for these representative matrices within a set of cardinality $(2^m-1)^5$. Through this method, we provide an explicit enumeration of the total number of $4 \times 4$ involutory MDS matrices over $\mathbb{F}_{2^m}$ for $m=3,4,\ldots,8$.

Related papers

• On the construction of ultra-light MDS matrices [4.739812980667592]
  We present an algorithm that efficiently enumerates all the lightest MDS matrices based on the word representation. We craft some involution $4times 4$ MDS matrices with a mere 68 XOR gates. These findings outperform the current state-of-the-art.
  arXiv  Detail & Related papers  (2024-09-05T07:07:41Z)
• 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. 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)
• Construction of all MDS and involutory MDS matrices [7.171901763517741]
  We propose two algorithms for a hybrid construction of all $ntimes n$ MDS and involutory MDS matrices over a finite field $mathbbF_pm$. The proposed algorithms effectively narrow down the search space to identify $(n-1) times (n-1)$ MDS matrices.
  arXiv  Detail & Related papers  (2024-03-15T15:03:02Z)
• 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)
• One-sided Matrix Completion from Two Observations Per Row [95.87811229292056]
  We propose a natural algorithm that involves imputing the missing values of the matrix $XTX$. We evaluate our algorithm on one-sided recovery of synthetic data and low-coverage genome sequencing.
  arXiv  Detail & Related papers  (2023-06-06T22:35:16Z)
• Batch-efficient EigenDecomposition for Small and Medium Matrices [65.67315418971688]
  EigenDecomposition (ED) is at the heart of many computer vision algorithms and applications. We propose a QR-based ED method dedicated to the application scenarios of computer vision.
  arXiv  Detail & Related papers  (2022-07-09T09:14:12Z)
• 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)
• What if Neural Networks had SVDs? [66.91160214071088]
  Various Neural Networks employ time-consuming matrix operations like matrix inversion. We present an algorithm that is fast enough to speed up several matrix operations.
  arXiv  Detail & Related papers  (2020-09-29T12:58:52Z)
• Sparsifying Parity-Check Matrices [60.28601275219819]
  We consider the problem of minimizing the number of one-entries in parity-check matrices. In the maximum-likelihood (ML) decoding method, the number of ones in PCMs is directly related to the time required to decode messages. We propose a simple matrix row manipulation which alters the PCM, but not the code itself.
  arXiv  Detail & Related papers  (2020-05-08T05:51:40Z)
• Sketching Transformed Matrices with Applications to Natural Language Processing [76.6222695417524]
  We propose a space-efficient sketching algorithm for computing the product of a given small matrix with the transformed matrix. We show that our approach obtains small error and is efficient in both space and time.
  arXiv  Detail & Related papers  (2020-02-23T03:07:31Z)

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.