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

Tianshuo Cong; Ximing Fu; Xuting Zhou; Yuli Zou; Haining Fan

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 $G F (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 and XOR gates for and matrices over respectively.

Metadata

Available format(s): PDF
Category: Implementation
Publication info: Preprint. MINOR revision.
Keywords: Lightweight cryptography MDS matrix Hadamard matrix Involution Subquadratic 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: 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},
      url = {https://eprint.iacr.org/2020/047}
}