On construction of lightweight MDS matrices

MDS matrices are widely used in block ciphers. Constructing lightweight MDS matrices is one of the research focuses of lightweight cryptography. In this paper, we define a new operation called the Copy operation by using registers. It is a generalization of Type 3 elementary operations (add a row to another one multiplied by a nonzero number). It is shown that any nonsingular matrix can be obtained by Copy operations and Multiplication operations from the identity matrix $ I $ (a Copy Block Implementation of the matrix). Thus we introduce a new metric called gw-xor using Copy Block Implementations to construct lightweight MDS matrices with respect to low xor gates. Compared with sw-xor, the gw-xor count is a better approximation of the optimal implementation cost, and in particular it may be a better approximation of the optimal implementation cost than s-xor. By searching the potential paths of Copy operations that can obtain formal MDS matrices (i.e., matrices with indeterminate elements and each determinant of square submatrix of any order is a nonzero polynomial in these indeterminates), we find 52 classes $ 16\times 16 $ and $ 32\times 32 $ binary MDS matrices with 35 and 67 xor gates respectively, which are the best known results. Furthermore, by considering the depth of MDS matrices, we find more $ 4\times4 $ MDS matrices over $ \mathbb{F}_{2^n} $ with the lowest xor gates at depths 3, 4, 5.