International Association
for Cryptologic Research

Ever since lightweight cryptography emerged as one of the trending topics in symmetric key cryptography, optimizing the implementation cost of MDS matrices has been in the center of attention. In this direction, various metrics like d-XOR, s-XOR and g-XOR have been proposed to mimic the hardware cost. Consequently, efforts also have been made to search for the optimal MDS matrices for dimensions relevant to cryptographic applications according to these metrics. However, finding the optimal MDS matrix in terms of hardware cost still remains an unsolved problem. In this paper, we settle the question of the optimal 4 x 4 MDS matrices over GL(n, F2) under the recently proposed metric sequential XOR count based on words (sw-XOR). We prove that the sw-XOR of such matrices is at least 8n + 3, and the bound is tight as matrices with sw-XOR cost 35 and 67 for the values of n = 4 and 8, respectively, were already known. Moreover, the lower bound for these values of n matches with the known lower bounds according to s-XOR and g-XOR metrics.

MDS matrices are used in the design of diffusion layers in many block ciphers and hash functions due to their optimal branch number. But MDS matrices, in general, have costly implementations. So in search for efficiently implementable MDS matrices, there have been many proposals. In particular, circulant, Hadamard, and recursive MDS matrices from companion matrices have been widely studied. In a recent work, recursive MDS matrices from sparse DSI matrices are studied, which are of interest due to their low fixed cost in hardware implementation. In this paper, we present results on the exhaustive search for (recursive) MDS matrices over GL(4, F2). Specifically, circulant MDS matrices of order 4, 5, 6, 7, 8; Hadamard MDS matrices of order 4, 8; recursive MDS matrices from companion matrices of order 4; recursive MDS matrices from sparse DSI matrices of order 4, 5, 6, 7, 8 are considered. It is to be noted that the exhaustive search is impractical with a naive approach. We first use some linear algebra tools to restrict the search to a smaller domain and then apply some space-time trade-off techniques to get the solutions. From the set of solutions in the restricted domain, one can easily generate all the solutions in the full domain. From the experimental results, we can see the (non) existence of (involutory) MDS matrices for the choices mentioned above. In particular, over GL(4, F2), we provide companion matrices of order 4 that yield involutory MDS matrices, circulant MDS matrices of order 8, and establish the nonexistence of involutory circulant MDS matrices of order 6, 8, circulant MDS matrices of order 7, sparse DSI matrices of order 4 that yield involutory MDS matrices, and sparse DSI matrices of order 5, 6, 7, 8 that yield MDS matrices. To the best of our knowledge, these results were not known before. For the choices mentioned above, if such MDS matrices exist, we provide base sets of MDS matrices, from which all the MDS matrices with the least cost (with respect to d-XOR and s-XOR counts) can be obtained. We also take this opportunity to present some results on the search for sparse DSI matrices over finite fields that yield MDS matrices. We establish that there is no sparse DSI matrix S of order 8 over F28 such that S8 is MDS.