International Association for Cryptologic Research

International Association
for Cryptologic Research


MDS Matrices with Lightweight Circuits

Sébastien Duval , Sorbonne Universités; UPMC Université Paris 06; Inria
Gaëtan Leurent , Inria
DOI: 10.13154/tosc.v2018.i2.48-78
Search ePrint
Search Google
Presentation: Slides
Abstract: MDS matrices are an important element for the design of block ciphers such as the AES. In recent years, there has been a lot of work on the construction of MDS matrices with a low implementation cost, in the context of lightweight cryptography. Most of the previous efforts focused on local optimization, constructing MDS matrices with coefficients that can be efficiently computed. In particular, this led to a matrix with a direct xor count of only 106, while a direct implementation of the MixColumn matrix of the AES requires 152 bitwise xors. More recently, techniques based on global optimization have been introduced, where the implementation can reuse some intermediate variables. In particular, Kranz et al. used optimization tools to find a good implementation from the description of an MDS matrix. They have lowered the cost of implementing the MixColumn matrix to 97 bitwise xors, and proposed a new matrix with only 72 bitwise xors, the lowest cost known so far. In this work we propose a different approach to global optimization. Instead of looking for an optimized circuit of a given matrix, we run a search through a space of circuits, to find optimal circuits yielding MDS matrices. This results in MDS matrices with an even lower cost, with only 67 bitwise xors.
Video from TOSC 2018
  title={MDS Matrices with Lightweight Circuits},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2018, Issue 2},
  author={Sébastien Duval and Gaëtan Leurent},