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


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.

Available format(s)
Publication info
Preprint. MINOR revision.
Lightweight cryptographyMDS matrixHadamard matrixInvolutionSubquadratic matrix-vector product
Contact author(s)
cts17 @ mails tsinghua edu cn
2020-01-18: revised
2020-01-17: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.