Article Preview
Top1. Introduction
Diffusion and confusion are two fundamental properties that must be considered when designing symmetric-key ciphers (Shannon, 1949). These two properties are required for the security of the cipher. The diffusion layer is often obtained by a linear diffusion matrix. Matrices with higher branch number perform better to resist linear and differential attacks. The matrix with the maximum branch number is perfect for constructing diffusion layers and called a Maximal Distance Separable (MDS) matrix.
MDS matrices are widely used in many ciphers, including AES (Daemen &Rijmen, 2002), LED (Guo, Peyrin, & Poschmann, 2011) and SQUARE (Daemen, Knudsen, & Rijmen, 1997). When resources are limited, it is necessary to reduce the implementation costs when designing diffusion layers. For MDS matrices, the construction of lightweight MDS matrices becomes a hot topic, where lightweight MDS matrices means MDS matrices with small XOR counts.
The general method of constructing MDS matrices is based on the matrices with some specific structures. Since searching for all the MDS matrices is beyond the reach, when the dimension of the matrix increases. Circulant matrices and Hadamard matrices are preferred due to their limited number of different elements, which also leads to a smaller number of different minors. Circulant-like MDS matrices were constructed and the lightest MDS circulant-like matrices were found in (Junod & Vaudenay, 2005; Gupta & Ray, 2014). In 2014, Khoo et al. (Khoo, Peyrin, Poschmann, & Yap, 2014) introduced the metric XOR count that measures the implementation cost of a diffusion matrix. Based on this metric, there are a lot of works. Sarkar and Syed (Sarkar & Syed, 2016) gave theoretical constructions of Toeplitz MDS matrices and reported the minimum value of the XOR counts of 4 × 4 MDS matrices over 
and 
, respectively. Li et al. (Li, Bai, Sun, & Wang, 2016) reported the minimum value of the XOR counts of 4 × 4 MDS matrices over 
.
Another way for constructing lightweight MDS matrices is by recursive construction. This method was used in the design of PHOTON lightweight hash family (Guo, Peyrin, & Poschmann, 2011) and LED lightweight block cipher (Guo, Peyrin, Poschmann & Robshaw, 2011)for the first time. Sajadieh et al. (Sajadieh, Dakhilalian, Mala, & Sepehrdad, 2015) extended the recursive method by using linear transformations instead of multiplications of elements infinite fields. It helps to increase the choices of entries in MDS matrices. Then Wu et al. (Wu, Wang, & Wu, 2013) presented some extreme lightweight MDS matrices by using linear transformations with fewer XORs. Toh et al. (Toh, Teo, Khoo, & Sim, 2017) proposed a new class of serial-type matrices known as Diagonal Serial Invertible (DSI) matrices.
Recently, Beierle et al. (Beierle, Kranz, & Leander, 2016) and Jean et al. (Jean, Peyrin, Sim, & Tourteaux, 2017) proposed the s-metric to reduce the implementation cost of diffusion matrices. By finding a short linear straight-line program to the case of MDS matrices, Kranz et al. (Kranz, Leander, Stoffelen, & Wiemer, 2017) optimized the previous constructions globally. Their metric can be applied to any matrix and they found that MDS matrices of special types do not differ much for all randomized constructions.
Contributions. In this paper, we study the constructions of MDS matrices and present a new metric to reduce the implementation cost of MDS matrices.
First, we present a new structure to construct MDS matrices over 
. Then we propose two conditions to construct MDS matrices and sufficient and necessary conditions under two different conditions are given.