New General MDS Matrix Construction Method Towards Low Area

Maximum Distance Separable (MDS) matrices have been widely used in symmetric cryptographic primitives because of their excellent cryptographic properties. However, due to the heavy area cost, larger-scale MDS matrices than 4 x 4 ones are limited in ciphers, although they have a larger branch number. In this paper, we propose a general method for constructing MDS matrices with low implementation area cost, using matrix decomposition, automatic search, and symbolic computation techniques. According to matrix decomposition theory, every invertible matrix can be decomposed into a sequence of elementary matrices, including Type-1 (row switching), Type-2 (row multiplication) and Type-3 (row addition) elementary matrices. So, we first propose a greedy algorithm to construct MDS matrix patterns with as few Type-3 elementary matrices as possible. Then, we build an automatic search model to minimize the implementation area of multiplication coefficients used in Type-3 elementary matrices. Lastly, another greedy strategy is raised to further reduce the implementation area of MDS matrix patterns by introducing a few Type-2 elementary matrices. In comparison to previous methods, our approach is more general and effective for constructing lower-area MDS matrices. To demonstrate the efficiency of our method, we apply the framework on constructing m x m MDS matrices over F2n or GL(n, F2), where m ∈ {4, 5, 6, 7, 8} and n ∈ {4, 8, 16, 32, 64}. The 4 x 4 MDS matrices constructed by our method can also reach the minimum area. The 5 x 5, 6 x 6 and 7 x 7 MDS matrices constructed by our method have lower area compared to previous ones. While the 8 x 8 MDS matrices with n ∈ {16, 32, 64} constructed by our method also have lower area compared to previous ones.