Construction of Recursive MDS Matrices Using DLS Matrices

Abstract

Many block ciphers and hash functions use MDS matrices because of their optimal branch number. On the other hand, MDS matrices generally have a high implementation cost, which makes them unsuitable for lightweight cryptographic primitives. In this direction, several sparse matrix structures like companion, GFS, and DSI matrices are proposed to construct recursive MDS matrices. The key benefit of these matrices is their low fixed XOR, and the diffusion layer can be made by recursively executing the implementation of the matrices, which takes a few clock cycles. In this paper, we propose a new class of sparse matrices called Diagonal-like sparse (DLS) matrices and the DSI matrix is a particular type of DLS matrix. We prove that for an n-MDS DLS matrix of order n, the fixed XOR (say K ) should be at least equal to the &#x2308

n2&#x2309

. We also show that an n-MDS DLS matrix over F2r with K=&#x2308

n2&#x2309

is a permutation similar to some n-MDS sparse DSI matrix. We propose another type of sparse matrices called generalized DLS (GDLS) matrices. Next, we introduce some lightweight recursive MDS matrices of orders 4, 5, 6, and 7, using GDLS matrices, that can be implemented with 22, 30, 31, and 45 XORs over F28, respectively. The results match the best known lightweight recursive MDS matrices of orders 4 and 6 and beat the best known matrices of orders 5 and 7. Also, the proposed 4-MDS GDLS matrix over F24 has a XOR count of 10, which meets the best known result. © 2022, The Author(s), under exclusive license to Springer Nature Switzerland AG.