Paper 2018/1072
Construction of MDS Matrices from Generalized Feistel Structures
Mahdi Sajadieh and Mohsen Mousavi
Abstract
This paper investigates the construction of 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. Moreover, we propose $8\times 8$ NearMDS matrices such that the implementation cost of the proposed matrices are $108$ and $204$ XOR for 4 and $8$bit input, respectively. Although none of the presented matrices are involutions, the implementation cost of the inverses of the proposed matrices is equal to the implementation cost of the given matrices. Furthermore, the construction presented in this paper is relatively general and can be applied for other matrix dimensions and finite fields as well.
Note: This is the last revised version of the paper.
Metadata
 Available format(s)
 Category
 Implementation
 Publication info
 Preprint.
 Keywords
 MDS matrixGeneralized Feistel StructuresDiffusion layer.
 Contact author(s)
 m mousavi @ mutes ac ir
 History
 20190529: last of 3 revisions
 20181109: received
 See all versions
 Short URL
 https://ia.cr/2018/1072
 License

CC BY
BibTeX
@misc{cryptoeprint:2018/1072, author = {Mahdi Sajadieh and Mohsen Mousavi}, title = {Construction of MDS Matrices from Generalized Feistel Structures}, howpublished = {Cryptology ePrint Archive, Paper 2018/1072}, year = {2018}, note = {\url{https://eprint.iacr.org/2018/1072}}, url = {https://eprint.iacr.org/2018/1072} }