On the Generalization of g-Circulant Matrices for Cryptographic MDS Matrix Construction
TL;DR
This paper generalizes circulant-type matrices over a finite field using the quotient rings to establish conditions related to their MDS, involutory, and semi-involutory properties and studies their invertibility, MDS, and involutory properties.
Abstract
Maximum distance separable (MDS) matrices are widely used as linear diffusion layers in symmetric-key cryptography because of their optimal branch number. In this paper, we generalize circulant-type matrices over a finite field <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{q}$ </tex-math></inline-formula> using the quotient rings <inline-formula> <tex-math notation="LaTeX">$\frac {\mathbb {F}_{q}[x]}{\langle x^{k}-\lambda \rangle }$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\frac {\mathbb {F}_{q}[x;\theta]}{\langle x^{k}-\lambda \rangle }$ </tex-math></inline-formula>, where <inline-formula> <tex-math notation="LaTeX">$\lambda \in \mathbb {F}_{q}^{*}$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$\theta :\mathbb {F}_{q}\rightarrow \mathbb {F}_{q}$ </tex-math></inline-formula> is a field automorphism. Using the first quotient ring, we introduce consta-<inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant matrices, which generalize circulant and <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant matrices. We study their invertibility, MDS, and involutory properties and give an explicit formula for the number of invertible consta-<inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant matrices. This formula reduces the search space for MDS testing, as shown in Table 3. The second quotient ring allows us to define consta-<inline-formula> <tex-math notation="LaTeX">$\theta _{g}$ </tex-math></inline-formula>-circulant matrices, extending <inline-formula> <tex-math notation="LaTeX">$\theta $ </tex-math></inline-formula>-circulant matrices through the parameters <inline-formula> <tex-math notation="LaTeX">$\lambda $ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>. We establish conditions related to their MDS, involutory, and semi-involutory properties. Over finite fields of characteristic 2, suitable Hadamard powers preserve these properties. Table 6 gives an exhaustive comparison for matrices of order 4 over <inline-formula> <tex-math notation="LaTeX">$\mathbb {F}_{7}$ </tex-math></inline-formula>. Among 2401 matrices for each fixed pair <inline-formula> <tex-math notation="LaTeX">$(\lambda,g)$ </tex-math></inline-formula>, no MDS matrix is obtained for <inline-formula> <tex-math notation="LaTeX">$(1,1)$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$(1,3)$ </tex-math></inline-formula>, whereas 48 MDS matrices are obtained for each of <inline-formula> <tex-math notation="LaTeX">$(6,1)$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$(6,3)$ </tex-math></inline-formula>. Thus, <inline-formula> <tex-math notation="LaTeX">$\lambda \neq 1$ </tex-math></inline-formula> produces MDS matrices not obtained in the circulant and <inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant cases with <inline-formula> <tex-math notation="LaTeX">$\lambda =1$ </tex-math></inline-formula>. This paper concludes with two open problems on orthogonal and involutory consta-<inline-formula> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula>-circulant MDS matrices over finite fields of characteristic 2.