**Construction of Lightweight MDS Matrices from Generalized Feistel Structures**

*Mahdi Sajadieh and Mohsen Mousavi*

**Abstract: **This paper investigates the construction of lightweight MDS matrices with generalized Feistel structures (GFS). The approach developed by this paper consists in deriving MDS matrices from the product of several sparser ones. This can be seen as a generalization to several matrices of the recursive construction which derives MDS matrices as the powers of a single companion matrix. The first part of this paper gives some theoretical results on the iteration of GFS and the second part gives concrete instantiations. The results match the best known lightweight $4\times 4$ MDS matrix and improve the best known $6\times 6$ and $8\times 8$ MDS matrices.
Based on GFS structure, we propose some types of sparse matrices that are called EGFS matrices. Then, by applying binary linear functions to several round of EGFS matrices, we propose lightweight $4\times 4$, $6\times 6$ and $8\times 8$ MDS matrices which are implemented with 67, 158 and 272 XOR for 8-bit input, respectively. The major work of this paper is the design of an $8\times 8$ MDS matrix with 272 XOR for 8-bit input, since the best known result is 392 XOR.

**Category / Keywords: **implementation / Lightweight cryptography, MDS matrix, Generalized Feistel Structures.

**Date: **received 4 Nov 2018

**Contact author: **m mousavi at mut-es ac ir

**Available format(s): **PDF | BibTeX Citation

**Version: **20181109:163134 (All versions of this report)

**Short URL: **ia.cr/2018/1072

[ Cryptology ePrint archive ]