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.
Type de document :
Communication dans un congrès
Pascale Charpin, Nicolas Sendrier, Jean-Pierre Tillich. The 9th International Workshop on Coding and Cryptography 2015 WCC2015, Apr 2015, Paris, France. 2015, Proceedings of the 9th International Workshop on Coding and Cryptography 2015 WCC2015
Liste complète des métadonnées

Littérature citée [13 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01276433
Contributeur : Jean-Pierre Tillich <>
Soumis le : vendredi 19 février 2016 - 13:18:48
Dernière modification le : samedi 28 juillet 2018 - 15:54:02
Document(s) archivé(s) le : vendredi 20 mai 2016 - 11:21:20

Fichier

wcc15-th1-3.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-01276433, version 1

Collections

Citation

Kishan Chand Gupta, Sumit Kumar Pandey, Ayineedi Venkateswarlu. On the Direct Construction of Recursive MDS Matrices. Pascale Charpin, Nicolas Sendrier, Jean-Pierre Tillich. The 9th International Workshop on Coding and Cryptography 2015 WCC2015, Apr 2015, Paris, France. 2015, Proceedings of the 9th International Workshop on Coding and Cryptography 2015 WCC2015. 〈hal-01276433〉

Partager

Métriques

Consultations de la notice

52

Téléchargements de fichiers

208