Paper 2016/186

Lightweight MDS Generalized Circulant Matrices (Full Version)

Meicheng Liu and Siang Meng Sim

Abstract

In this article, we analyze the circulant structure of generalized circulant matrices to reduce the search space for finding lightweight MDS matrices. We first show that the implementation of circulant matrices can be serialized and can achieve similar area requirement and clock cycle performance as a serial-based implementation. By proving many new properties and equivalence classes for circulant matrices, we greatly reduce the search space for finding lightweight maximum distance separable (MDS) circulant matrices. We also generalize the circulant structure and propose a new class of matrices, called cyclic matrices, which preserve the benefits of circulant matrices and, in addition, have the potential of being self-invertible. In this new class of matrices, we obtain not only the MDS matrices with the least XOR gates requirement for dimensions from 3x3 to 8x8 in GF(2^4) and GF(2^8), but also involutory MDS matrices which was proven to be non-existence in the class of circulant matrices. To the best of our knowledge, the latter matrices are the first of its kind, which have a similar matrix structure as circulant matrices and are involutory and MDS simultaneously. Compared to the existing best known lightweight matrices, our new candidates either outperform or match them in terms of XOR gates required for a hardware implementation. Notably, our work is generic and independent of the metric for lightweight. Hence, our work is applicable for improving the search for efficient circulant matrices under other metrics besides XOR gates.

Note: Corrected the typo in the 7x7 IMDS left-circulant matrices.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in FSE 2016
Keywords
lightweight cryptographydiffusion layerMDScirculant matrices
Contact author(s)
ssim011 @ e ntu edu sg
History
2017-04-25: last of 3 revisions
2016-02-23: received
See all versions
Short URL
https://ia.cr/2016/186
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/186,
      author = {Meicheng Liu and Siang Meng Sim},
      title = {Lightweight MDS Generalized Circulant Matrices (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2016/186},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/186}},
      url = {https://eprint.iacr.org/2016/186}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.