Paper 2016/406

On the Construction of Lightweight Circulant Involutory MDS Matrices

Yongqiang Li and Mingsheng Wang


In the present paper, we investigate the problem of constructing MDS matrices with as few bit XOR operations as possible. The key contribution of the present paper is constructing MDS matrices with entries in the set of $m\times m$ non-singular matrices over $\mathbb{F}_2$ directly, and the linear transformations we used to construct MDS matrices are not assumed pairwise commutative. With this method, it is shown that circulant involutory MDS matrices, which have been proved do not exist over the finite field $\mathbb{F}_{2^m}$, can be constructed by using non-commutative entries. Some constructions of $4\times4$ and $5\times5$ circulant involutory MDS matrices are given when $m=4,8$. To the best of our knowledge, it is the first time that circulant involutory MDS matrices have been constructed. Furthermore, some lower bounds on XORs that required to evaluate one row of circulant and Hadamard MDS matrices of order 4 are given when $m=4,8$. Some constructions achieving the bound are also given, which have fewer XORs than previous constructions.

Available format(s)
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2016
Contact author(s)
yongq lee @ gmail com
2016-04-25: received
Short URL
Creative Commons Attribution


      author = {Yongqiang Li and Mingsheng Wang},
      title = {On the Construction of Lightweight Circulant Involutory MDS Matrices},
      howpublished = {Cryptology ePrint Archive, Paper 2016/406},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.