Paper 2020/047

New Subquadratic Algorithms for Constructing Lightweight Hadamard MDS Matrices (Full Version)

Tianshuo Cong, Ximing Fu, Xuting Zhou, Yuli Zou, and Haining Fan

Abstract

Maximum Distance Separable (MDS) Matrix plays a crucial role in designing cryptosystems. In this paper we mainly talk about constructing lightweight Hadamard MDS matrices based on subquadratic multipliers over $GF(2^4)$. We firstly propose subquadratic Hadamard matrix-vector product formulae (HMVP), and provide two new XOR count metrics. To the best of our knowledge, subquadratic multipliers have not been used to construct MDS matrices. Furthermore, combined with HMVP formulae we design a construction algorithm to find lightweight Hadamard MDS matrices under our XOR count metric. Applying our algorithms, we successfully find MDS matrices with the state-of-the-art fewest XOR counts for $4 \times 4$ and $8 \times 8$ involutory and non-involutory MDS matrices. Experiment results show that our candidates save up to $40.63\%$ and $10.34\%$ XOR gates for $8 \times 8$ and $4 \times 4$ matrices over $GF(2^4)$ respectively.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint. MINOR revision.
Keywords
Lightweight cryptographyMDS matrixHadamard matrixInvolutionSubquadratic matrix-vector product
Contact author(s)
cts17 @ mails tsinghua edu cn
History
2020-01-18: revised
2020-01-17: received
See all versions
Short URL
https://ia.cr/2020/047
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/047,
      author = {Tianshuo Cong and Ximing Fu and Xuting Zhou and Yuli Zou and Haining Fan},
      title = {New Subquadratic Algorithms for Constructing Lightweight Hadamard MDS Matrices (Full Version)},
      howpublished = {Cryptology ePrint Archive, Paper 2020/047},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/047}},
      url = {https://eprint.iacr.org/2020/047}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.