MDS matrices from skew polynomials with automorphisms and derivations

Maximum Distance Separable (MDS) matrices play a central role in coding theory and symmetric-key cryptography due to their optimal diffusion properties. In this paper, we present a construction of MDS matrices using skew polynomial rings ${\mathbb{F}}_q[X;\theta ,\delta ]$, where $\theta$ is an automorphism and $\delta$ is a $\theta$-derivation on ${\mathbb{F}}_q$. We introduce the notion of ${\delta }_{\theta }$-circulant matrices and study their structural properties. Necessary and sufficient conditions are derived under which these matrices are involutory and satisfy the MDS property. The resulting ${\delta }_{\theta }$-circulant matrix can be viewed as a generalization of classical constructions obtained in the absence of $\theta$-derivations. One of the main contribution of this work is the construction of quasi recursive MDS matrices. In the setting of the skew polynomial ring ${\mathbb{F}}_q[X;\theta ]$, we construct quasi recursive MDS matrices associated with companion matrices. These matrices are shown to be involutory, yielding a strict improvement over the quasi-involutory constructions previously reported in the literature. Several illustrative results and examples are also provided.