Shorter Linear Straight-Line Programs for MDS Matrices

Thorsten Kranz; Gregor Leander; Ko Stoffelen; Friedrich Wiemer

Paper 2017/1151

Shorter Linear Straight-Line Programs for MDS Matrices

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

Abstract

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

Metadata

Available format(s): PDF
Category: Implementation
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
History: 2020-03-31: last of 4 revisions; 2017-11-27: received; See all versions
Short URL: https://ia.cr/2017/1151
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1151,
      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},
      url = {https://eprint.iacr.org/2017/1151}
}