Paper 2017/1151

Shorter Linear Straight-Line Programs for MDS Matrices

Thorsten Kranz, Gregor Leander, Ko Stoffelen, and Friedrich Wiemer


Recently a lot of attention is paid to the search for efficiently implementable MDS matrices for lightweight symmetric primitives. Previous work concentrated on locally optimizing the multiplication with single matrix elements. Separate from this line of work, several heuristics were developed to find shortest linear straight-line programs. Solving this problem actually corresponds to globally optimizing multiplications by matrices. In this work we combine those, so far largely independent line of works. As a result, we achieve implementations of known, locally optimized, and new MDS matrices that significantly outperform all implementations from the literature. Interestingly, almost all previous locally optimized constructions behave very similar with respect to the globally optimized implementation. As a side effect, our work reveals the so far best implementation of the AES MixColumns operation with respect to the number of XOR operations needed.

Note: fixed accents in previous version

Available format(s)
Publication info
A minor revision of an IACR publication in FSE 2018
Contact author(s)
thorsten kranz @ rub de
gregor leander @ rub de
k stoffelen @ cs ru nl
friedrich wiemer @ rub de
2020-03-31: last of 4 revisions
2017-11-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thorsten Kranz and Gregor Leander and Ko Stoffelen and Friedrich Wiemer},
      title = {Shorter Linear Straight-Line Programs for MDS Matrices},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1151},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.