Construction methods for MDS matrices using companion and permutation matrices for lightweight cryptography

In this work, we propose a new construction method of MDS-matrices of dimension $k = 4, 6$ by means of summation of a power $r$ of the companion matrix of a certain polynomial and a fixed permutation matrix over the finite field $\mathrm{GF}(2^8) $. The method is represented by the expression $S_f^r + P$ for a polynomial $f(x)=x^k+f_{k-1}x^{k-1}+\ldots+f_1x+f_0$, where $S_f$ is the companion matrix of the polynomial $f(x)$, $P$ is a permutation matrix, $r={3k}/{2}$, and the coefficients $f_i\in\{0,1,\alpha,\alpha^{-1},\alpha^2,\alpha^3\}$. For its effective implementation, it is proposed to apply $S_f$ as a linear feedback shift register with characteristic polynomial $f(x)$ and $P$ as a Feistel network with $k$ entrances. The XOR-count metric is used to show the effectiveness of the proposed method in algorithms that require low implementation cost.