Related papers: A note on cyclic non-MDS matrices

A note on cyclic non-MDS matrices

URL: http://arxiv.org/abs/2406.14013v1
Date: Thu, 20 Jun 2024 06:05:16 GMT
Title: A note on cyclic non-MDS matrices
Authors: Tapas Chatterjee, Ayantika Laha,
Abstract summary: In $1998,$ Daemen it et al. introduced a circulant Maximum Distance Separable (MDS) matrix in the diffusion layer of the Rijndael block cipher. This block cipher is now universally acclaimed as the AES block cipher. In $2016,$ Liu and Sim introduced cyclic matrices by modifying the permutation of circulant matrices.
Score: 3.069335774032178
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: In $1998,$ Daemen {\it{ et al.}} introduced a circulant Maximum Distance Separable (MDS) matrix in the diffusion layer of the Rijndael block cipher, drawing significant attention to circulant MDS matrices. This block cipher is now universally acclaimed as the AES block cipher. In $2016,$ Liu and Sim introduced cyclic matrices by modifying the permutation of circulant matrices and established the existence of MDS property for orthogonal left-circulant matrices, a notable subclass within cyclic matrices. While circulant matrices have been well-studied in the literature, the properties of cyclic matrices are not. Back in $1961$, Friedman introduced $g$-circulant matrices which form a subclass of cyclic matrices. In this article, we first establish a permutation equivalence between a cyclic matrix and a circulant matrix. We explore properties of cyclic matrices similar to $g$-circulant matrices. Additionally, we determine the determinant of $g$-circulant matrices of order $2^d \times 2^d$ and prove that they cannot be simultaneously orthogonal and MDS over a finite field of characteristic $2$. Furthermore, we prove that this result holds for any cyclic matrix.

Related papers

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.
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. 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)
Factor Fitting, Rank Allocation, and Partitioning in Multilevel Low Rank Matrices [43.644985364099036]
We address three problems that arise in fitting a given matrix by an MLR matrix in the Frobenius norm. The first problem is factor fitting, where we adjust the factors of the MLR matrix. The second is rank allocation, where we choose the ranks of the blocks in each level, subject to the total rank having a given value. The final problem is to choose the hierarchical partition of rows and columns, along with the ranks and factors.
arXiv Detail & Related papers (2023-10-30T00:52:17Z)
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)
Quantum algorithms for matrix operations and linear systems of equations [65.62256987706128]
We propose quantum algorithms for matrix operations using the "Sender-Receiver" model. These quantum protocols can be used as subroutines in other quantum schemes.
arXiv Detail & Related papers (2022-02-10T08:12:20Z)
Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors [54.936314353063494]
We provide recovery guarantees for a correlation-based optimization algorithm for robust 1-bit compressive sensing. We make use of a practical iterative algorithm, and perform numerical experiments on image datasets to corroborate our results.
arXiv Detail & Related papers (2021-08-08T05:28:06Z)
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)
Algebraic and geometric structures inside the Birkhoff polytope [0.0]
Birkhoff polytope $mathcalB_d$ consists of all bistochastic matrices of order $d$. We prove that $mathcalL_d$ and $mathcalF_d$ are star-shaped with respect to the flat matrix.
arXiv Detail & Related papers (2021-01-27T09:51:24Z)

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