Paper 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in FSE 2017
Keywords
Toeplitz matrixMDS matrixXOR countInvolutory MDS matrixdiffusion layerLightweight block cipher
Contact author(s)
sumanta sarkar @ gmail com
History
2016-09-30: last of 2 revisions
2016-08-31: received
See all versions
Short URL
https://ia.cr/2016/835
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/835,
      author = {Sumanta Sarkar and Habeeb Syed},
      title = {Lightweight Diffusion Layer: Importance of Toeplitz Matrices},
      howpublished = {Cryptology ePrint Archive, Paper 2016/835},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/835}},
      url = {https://eprint.iacr.org/2016/835}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.