Cryptology ePrint Archive: Report 2020/047

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

Tianshuo Cong and Ximing Fu and Xuting Zhou and 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.

Category / Keywords: implementation / Lightweight cryptography; MDS matrix; Hadamard matrix; Involution; Subquadratic matrix-vector product

Date: received 16 Jan 2020, last revised 17 Jan 2020

Contact author: cts17 at mails tsinghua edu cn

Available format(s): PDF | BibTeX Citation

Version: 20200118:034145 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]