Cryptology ePrint Archive: Report 2015/258

Lightweight MDS Involution Matrices

Siang Meng Sim and Khoongming Khoo and Frédérique Oggier and Thomas Peyrin

Abstract: In this article, we provide new methods to look for lightweight MDS matrices, and in particular involutory ones. By proving many new properties and equivalence classes for various MDS matrices constructions such as circulant, Hadamard, Cauchy and Hadamard-Cauchy, we exhibit new search algorithms that greatly reduce the search space and make lightweight MDS matrices of rather high dimension possible to find. We also explain why the choice of the irreducible polynomial might have a significant impact on the lightweightness, and in contrary to the classical belief, we show that the Hamming weight has no direct impact. Even though we focused our studies on involutory MDS matrices, we also obtained results for non-involutory MDS matrices. Overall, using Hadamard or Hadamard-Cauchy constructions, we provide the (involutory or non-involutory) MDS matrices with the least possible XOR gates for the classical dimensions 4x4, 8x8, 16x16 and 32x32 in GF(2^4) and GF(2^8). Compared to the best known matrices, some of our new candidates save up to 50% on the amount of XOR gates required for an hardware implementation. Finally, our work indicates that involutory MDS matrices are really interesting building blocks for designers as they can be implemented with almost the same number of XOR gates as non-involutory MDS matrices, the latter being usually non-lightweight when the inverse matrix is required.

Category / Keywords: lightweight cryptography, Hadamard matrix, Cauchy matrix, involution, MDS

Original Publication (with minor differences): IACR-FSE-2015

Date: received 19 Mar 2015, last revised 28 May 2015

Contact author: ssim011 at e ntu edu sg

Available format(s): PDF | BibTeX Citation

Note: Minor typo in the entry of the 32x32 involutory MDS matrix

Version: 20190217:224315 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]