Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes

Daniel Augot; Matthieu Finiasz

Paper 2014/566

Direct Construction of Recursive MDS Diffusion Layers using Shortened BCH Codes

Daniel Augot and Matthieu Finiasz

Abstract

MDS matrices allow to build optimal linear diffusion layers in block ciphers. However, MDS matrices cannot be sparse and usually have a large description, inducing costly software/hardware implementations. Recursive MDS matrices allow to solve this problem by focusing on MDS matrices that can be computed as a power of a simple companion matrix, thus having a compact description suitable even for constrained environments. However, up to now, finding recursive MDS matrices required to perform an exhaustive search on families of companion matrices, thus limiting the size of MDS matrices one could look for. In this article we propose a new direct construction based on shortened BCH codes, allowing to efficiently construct such matrices for whatever parameters. Unfortunately, not all recursive MDS matrices can be obtained from BCH codes, and our algorithm is not always guaranteed to find the best matrices for a given set of parameters.

Note: Typo in Finiasz given name

Metadata

Available format(s): PDF
Category: Secret-key cryptography
Publication info: Published by the IACR in FSE 2014
Contact author(s): Daniel Augot @ inria fr
History: 2014-07-22: received
Short URL: https://ia.cr/2014/566
License: CC BY

BibTeX

@misc{cryptoeprint:2014/566,
      author = {Daniel Augot and Matthieu Finiasz},
      title = {Direct Construction of Recursive {MDS} Diffusion Layers using Shortened {BCH} Codes},
      howpublished = {Cryptology {ePrint} Archive, Paper 2014/566},
      year = {2014},
      url = {https://eprint.iacr.org/2014/566}
}