On the Construction of New Lightweight Involutory MDS Matrices in Generalized Subfield Form

Abstract

Maximum Distance Separable (MDS) matrices are used as the main component of diffusion layers in block ciphers. MDS matrices have the optimal diffusion properties and the maximum branch number, which is a criterion to measure diffusion rate and security against linear and differential crypt analysis. However, it is a challenging problem to construct hardware-friendly MDS matrices with optimal or close to optimal circuits, especially for involutory ones. In this paper, we consider the generalized subfield construction method from the global optimization perspective and then give new 4 x 4 involutory MDS matrices over F-2(3) and F-2(5). After that, we present 1,176 (= 28 x 42) new 4 x 4 involutory and MDS diffusion matrices by 33 XORs and depth 3. This new record also improves the previously best-known cost of 38 XOR gates.