International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Shorter Linear Straight-Line Programs for MDS Matrices

Authors:
Thorsten Kranz , Horst Görtz Institute for IT Security, Ruhr-Universität Bochum
Gregor Leander , Horst Görtz Institute for IT Security, Ruhr-Universität Bochum
Ko Stoffelen , Digital Security Group, Radboud University, Nijmegen
Friedrich Wiemer , Horst Görtz Institute for IT Security, Ruhr-Universität Bochum
Download:
DOI: 10.13154/tosc.v2017.i4.188-211
URL: https://tosc.iacr.org/index.php/ToSC/article/view/813
Search ePrint
Search Google
Abstract: Recently a lot of attention is paid to the search for efficiently implementable MDS matrices for lightweight symmetric primitives. Most 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 straightline programs. Solving this problem actually corresponds to globally optimizing multiplications by matrices. In this work we combine those, so far largely independent lines of work. 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 Mix- Columns operation with respect to the number of XOR operations needed.
BibTeX
@article{tosc-2017-28471,
  title={Shorter Linear Straight-Line Programs for MDS Matrices},
  journal={IACR Trans. Symmetric Cryptol.},
  publisher={Ruhr-Universität Bochum},
  volume={2017, Issue 4},
  pages={188-211},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/813},
  doi={10.13154/tosc.v2017.i4.188-211},
  author={Thorsten Kranz and Gregor Leander and Ko Stoffelen and Friedrich Wiemer},
  year=2017
}