Paper 2013/056

On Constructions of MDS Matrices from Companion Matrices for Lightweight Cryptography

Kishan Chand Gupta and Indranil Ghosh Ray

Abstract

Maximum distance separable (MDS) matrices have applications not only in coding theory but also are of great importance in the design of block ciphers and hash functions. It is highly nontrivial to find MDS matrices which could be used in lightweight cryptography. In a crypto 2011 paper, Guo et. al. proposed a new MDS matrix $Serial(1,2,1,4)^4$ over $\mathbb{F}_{2^8}$. This representation has a compact hardware implementation of the AES MixColumn operation. No general study of MDS properties of this newly introduced construction of the form $Serial(z_0,\ldots,z_{d-1})^d$ over $\mathbb{F}_{2^n}$ for arbitrary $d$ and $n$ is available in the literature. In this paper we study some properties of MDS matrices and provide an insight of why $Serial(z_0,\ldots,z_{d-1})^d$ leads to an MDS matrix. For efficient hardware implementation, we aim to restrict the values of $z_i$'s in $\{1,\alpha,\alpha^2,\alpha+1\}$, such that $Serial(z_0,\ldots,z_{d-1})^d$ is MDS for $d = 4 \mbox{ and } 5$, where $\alpha$ is the root of the constructing polynomial of $\mathbb{F}_{2^n}$. We also propose more generic constructions of MDS matrices e.g. we construct lightweight $4 \times 4$ and $5 \times 5$ MDS matrices over $\mathbb{F}_{2^n}$ for all $n \ge 4$. An algorithm is presented to check if a given matrix is MDS. The algorithm directly follows from the basic properties of MDS matrix and is easy to implement.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
kishan @ isical ac in
History
2013-02-06: received
Short URL
https://ia.cr/2013/056
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/056,
      author = {Kishan Chand Gupta and Indranil Ghosh Ray},
      title = {On Constructions of MDS Matrices from Companion Matrices for Lightweight Cryptography},
      howpublished = {Cryptology ePrint Archive, Paper 2013/056},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/056}},
      url = {https://eprint.iacr.org/2013/056}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.