Cryptology ePrint Archive: Report 2016/835

Lightweight Diffusion Layer: Importance of Toeplitz Matrices

Sumanta Sarkar and Habeeb Syed

Abstract: MDS matrices are used as building blocks of diffusion layers in block ciphers, and XOR count is a metric that estimates the hardware implementation cost. In this paper we report the minimum value of XOR counts of $4 \times 4$ MDS matrices over $\mathbb{F}_{2^4}$ and $\mathbb{F}_{2^8}$, respectively. We give theoretical constructions of Toeplitz MDS matrices and show that they achieve the minimum XOR count. We also prove that Toeplitz matrices cannot be both MDS and involutory. Further we give theoretical constructions of $4 \times 4$ involutory MDS matrices over $\mathbb{F}_{2^4}$ and $\mathbb{F}_{2^8}$ that have the best known XOR counts so far: for $\mathbb{F}_{2^4}$ our construction gives an involutory MDS matrix that actually improves the existing lower bound of XOR count, whereas for $\mathbb{F}_{2^8}$, it meets the known lower bound.

Category / Keywords: Toeplitz matrix, MDS matrix, XOR count, Involutory MDS matrix, diffusion layer, Lightweight block cipher

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

Date: received 29 Aug 2016, last revised 30 Sep 2016

Contact author: sumanta sarkar at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20160930:065710 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]