Cryptology ePrint Archive: Report 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 \textit{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 $3 \times 3$ to $8 \times 8$ 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.

Category / Keywords: lightweight cryptography, diffusion layer, MDS, circulant matrices

Original Publication (in the same form): IACR-FSE-2016

Date: received 22 Feb 2016, last revised 29 Apr 2016

Contact author: ssim011 at e ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20160429:093740 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]