A systematic construction approach for all \(4\times 4\) involutory MDS matrices

Maximum distance separable (MDS) matrices play a crucial role not only in coding theory but also in the design of block ciphers and hash functions. Of particular interest are involutory MDS matrices, which facilitate the use of a single circuit for both encryption and decryption in hardware implementations. In this article, we present several characterizations of involutory MDS matrices of even order. Additionally, we introduce a new matrix form for obtaining all involutory MDS matrices of even order and compare it with other matrix forms available in the literature. We then propose a technique to systematically construct all \(4 \times 4\) $4\times 4$ involutory MDS matrices over a finite field \(\mathbb {F}_{2^m}\) ${\mathbb{F}}_{2^m}$ . This method significantly reduces the search space by focusing on involutory MDS class representative matrices, leading to the generation of all such matrices within a substantially smaller set compared to considering all \(4 \times 4\) $4\times 4$ involutory matrices. Specifically, our approach involves searching for these representative matrices within a set of cardinality \((2^m-1)^5\) ${(2^m-1)}^5$ . Through this method, we provide an explicit enumeration of the total number of \(4 \times 4\) $4\times 4$ involutory MDS matrices over \(\mathbb {F}_{2^m}\) ${\mathbb{F}}_{2^m}$ for \(m=3,4,\ldots ,8\) $m=3,4,\dots ,8$ .