On the construction of ultra-light MDS matrices

• URL: http://arxiv.org/abs/2409.03298v1
• Date: Thu, 5 Sep 2024 07:07:41 GMT
• Title: On the construction of ultra-light MDS matrices
• Authors: Yu Tian, Xiutao Feng, Guangrong Li,
• Abstract summary: 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.
• Score: 4.739812980667592
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In recent years, the Substitution-Permutation Network has emerged as a crucial structure for constructing symmetric key ciphers. Composed primarily of linear matrices and nonlinear S-boxes, it offers a robust foundation for cryptographic security. Among the various metrics used to assess the cryptographic properties of linear matrices, the branch number stands out as a particularly important index. Matrices with an optimal branch number are referred to as MDS matrices and are highly prized in the field of cryptography. In this paper we delve into the construction of lightweight MDS matrices. We commence implementation trees of MDS matrices, which is a vital tool for understanding and manipulating their implementations, and then present an algorithm that efficiently enumerates all the lightest MDS matrices based on the word representation. As results, we obtain a series of ultra-lightweight $4\times 4$ MDS matrices, remarkably, 4-bit input MDS matrices with 35 XOR operations and 8-bit input ones with 67 XOR operations . These matrices represent the most comprehensive lightweight MDS matrices available to date. Furthermore, we craft some involution $4\times 4$ MDS matrices with a mere 68 XOR gates.To our best knowledge, they are the best up to date. In the realm of higher-order MDS matrices, we have successfully constructed $5\times 5$ and $6\times 6$ matrices with 114 and 148 XOR gates respectively. These findings outperform the current state-of-the-art.

Related papers

• 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)
• 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)
• Large-scale gradient-based training of Mixtures of Factor Analyzers [67.21722742907981]
  This article contributes both a theoretical analysis as well as a new method for efficient high-dimensional training by gradient descent. We prove that MFA training and inference/sampling can be performed based on precision matrices, which does not require matrix inversions after training is completed. Besides the theoretical analysis and matrices, we apply MFA to typical image datasets such as SVHN and MNIST, and demonstrate the ability to perform sample generation and outlier detection.
  arXiv  Detail & Related papers  (2023-08-26T06:12:33Z)
• On the Direct Construction of MDS and Near-MDS Matrices [6.356706243374352]
  Near-MDS (NMDS) matrices with sub-optimal branch numbers offer a better balance between security and efficiency as a diffusion layer. This paper introduces some direct constructions of NMDS matrices in both nonrecursive and recursion settings. We propose a method for constructing involutory MDS and NMDS matrices using generalized Vandermonde matrices.
  arXiv  Detail & Related papers  (2023-06-22T12:43:53Z)
• 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)
• 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.