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 (with minor differences): IACR-FSE-2018

Date: received 27 Nov 2017, last revised 31 Mar 2020

Contact author: thorsten kranz at rub de, gregor leander@rub de, k stoffelen@cs ru nl, friedrich wiemer@rub de