On the Direct Construction of Recursive MDS Matrices

Abstract : MDS matrices allow to build optimal linear diffusion layers in the design of block ciphers and hash functions. There has been a lot of study in designing efficient MDS matrices suitable for software and/or hardware implementations. In particular recursive MDS matrices are considered for resource constrained environments. Such matrices can be computed as a power of simple companion matrices, i.e., an MDS matrix M = C k g for some companion matrix corresponding to a polynomial g(X) ∈ Fq[X] of degree k. In this paper we first show that if the polynomial g(X) has no multiple of weight ≤ k and degree ≤ 2k − 1 then the matrix M = C^k_g satisfies MDS property. In fact, we show that the corresponding MDS code M is a shortened code of the cyclic code Γ defined by g(X) (code words of M are given by the multiples of g(X) with degree at most 2k − 1). This characterization answers the issues raised by Agout et. al. in FSE-2014 paper to some extent. We then revisit Augot et al. method (FSE-2014) to construct recursive MDS matrices using shortened BCH codes (which are also MDS) and propose an improved method. Our method improves upon their method by confining the computation to only the potential cases where we are guaranteed to get recursive MDS matrices, and thus greatly reducing the complexity. As a consequence we are able to provide formula for the number of such recursive MDS matrices, whereas in FSE-2014 paper, the same numbers are provided by exhaustively searching for some small parameter choices. We also present a few ideas making the search faster for finding efficient recursive MDS matrices in this class. Using our approach it is possible to exhaustively search this class for some bigger parameter choices which was not possible earlier.