Paper 2018/260

MDS Matrices with Lightweight Circuits

Sébastien Duval and Gaëtan Leurent


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, were the implementation can reuse some intermediate variables. In particular, Kranz \emph{et al.} used optimization tools to a find 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.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
MDS matrixlightweight cryptography
Contact author(s)
sebastien duval @ inria fr
2018-03-09: received
Short URL
Creative Commons Attribution


      author = {Sébastien Duval and Gaëtan Leurent},
      title = {MDS Matrices with Lightweight Circuits},
      howpublished = {Cryptology ePrint Archive, Paper 2018/260},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.