**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. In second part, using GFS and primitive matrices,
we propose some types of sparse matrices that are called
extended primitive GFS (EGFS) matrices.
Then, by applying binary linear functions to several round of EGFS matrices,
lightweight $4\times 4$, $6\times 6$ and $8\times 8$ MDS matrices are proposed
which are implemented with 67, 156 and 260 XOR for 8-bit input, respectively.
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.
Also, the proposed $6\times 6$ MDS matrix is implemented with
114 XOR for 6-bit input.
Moreover, we propose an $6\times 6$ MDS matrix such that
the implementation cost of the proposed matrix is 90 XOR for 4-bit input.
Furthermore, we determine the implementation cost of the inverses of the proposed matrices, since none of
them are involutions. Generally, the construction presented in this paper is relatively general
and can be applied for other matrix dimensions and finite fields as well.

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

**Date: **received 4 Nov 2018, last revised 1 Feb 2019

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

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

**Note: **This is the first revised version of the paper.

**Version: **20190201:194233 (All versions of this report)

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

[ Cryptology ePrint archive ]