Skip to Main content Skip to Navigation
Conference papers

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.
Complete list of metadata

Cited literature [13 references]  Display  Hide  Download
Contributor : Jean-Pierre Tillich <>
Submitted on : Friday, February 19, 2016 - 1:18:48 PM
Last modification on : Sunday, July 28, 2019 - 9:22:02 AM
Long-term archiving on: : Friday, May 20, 2016 - 11:21:20 AM


Files produced by the author(s)


  • HAL Id : hal-01276433, version 1



Kishan Chand Gupta, Sumit Kumar Pandey, Ayineedi Venkateswarlu. On the Direct Construction of Recursive MDS Matrices. The 9th International Workshop on Coding and Cryptography 2015 WCC2015, Anne Canteaut, Gaëtan Leurent, Maria Naya-Plasencia, Apr 2015, Paris, France. ⟨hal-01276433⟩



Record views


Files downloads