Cryptology ePrint Archive: Report 2017/1151

Shorter Linear Straight-Line Programs for MDS Matrices

Thorsten Kranz and Gregor Leander and 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.

Category / Keywords: implementation / XOR Count and MDS and Linear Layer and Shortest Straight-Line Program and SAT

Original Publication (in the same form): IACR-FSE-2018

Date: received 27 Nov 2017, last revised 28 Nov 2017

Contact author: thorsten kranz at rub de

Available format(s): PDF | BibTeX Citation

Note: Changed Contact Email.

Version: 20171128:084436 (All versions of this report)

Short URL: ia.cr/2017/1151

Discussion forum: Show discussion | Start new discussion