Paper 2018/1072

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.