Construction of lightweight involutory MDS matrices

In this paper, we propose an efficient method to find lightweight involutory MDS matrices. To obtain involutory matrices, we give a necessary and sufficient condition for judging the involutory MDS property and propose a search method. For the \(n\times n\) involutory MDS matrices over \({\mathbb {F}}_{2^m}\), the amount of computation is reduced from \(2^{mn^2}\) to \(2^{(mn^2)/2}\). Especially, we can exhaustively search for involutory MDS matrices when \(n=4\), and for larger n, we add additional restrictions to reduce the search range. As for finding lightweight ones, we use the permutation-equivalent class to extend the input such that the efficiency of the heuristic designed by Xiang et al. can be improved. Applying our method, we obtain a class of \(16\times 16\) binary MDS matrices with branch number 5, which can be implemented with only 35 XOR gates. The results even reach the same implementation cost as the lightest non-involutory MDS matrix up to now. Concerning lightweight binary matrices with order 32, it is hard to obtain optimal results through search. Hence, we construct \(32\times 32\) matrices with the lightweight \(16 \times 16\) matrices that we found. In this way, we obtain two classes of \( 4 \times 4 \) involutory MDS matrices whose entries are \( 8 \times 8 \) binary matrices with 70 XOR gates while the previous lightest matrices with the same size cost 78 XOR gates. Moreover, we also generalize our search method to general cases and it is provable that the approach is feasible for MDS matrices of order 6 and 8 to achieve efficient search.