Cryptology ePrint Archive: Report 2016/1173

Construction of Lightweight MDS Matrices over the Matrix Polynomial Residue Ring

Lijing Zhou, Licheng Wang and Yiru Sun

Abstract: Firstly, by analyzing non-singular matrices with few XORs in the matrix polynomial residue ring, we present an efficient method for building lightweight maximum distance separable (MDS) matrices with elements chosen from a fixed matrix polynomial residue ring. Compared with that constructions of previous methods usually cost several days or several weeks, our new method only cost within several minutes. With this method, many different types of lightweight MDS matrices can be quickly constructed. This method has a significance for researching the lightweight MDS matrix. Surprisingly, it did not receive much attention previously. We give 5 matrix templates which are suitable to construct lightweight MDS matrices. Secondly, we investigate the existence of involutory MDS matrix for several matrix templates. Besides, we present an efficient necessary-and-sufficient condition for judging whether a Hadamard matrix is involutory. With this condition, an extremely efficient algorithm for constructing lightweight Hadamard involutory MDS matrices is given. By doing experiments, we get a lot of new Hadamard involutory MDS matrices with much fewer XORs than previously optimal results. Thirdly, in theory, we discuss reasons about why our methods work very efficiently. Finally, we prove a series of propositions about the parity of XORs of element-matrix and entirety-matrix.

Category / Keywords: MDS matrix, XOR count, matrix polynomial residue ring, involutory matrix

Date: received 20 Dec 2016, last revised 13 Jun 2017

Contact author: 379739494 at qq com

Available format(s): PDF | BibTeX Citation

Note: Publish the full version of my paper.

Version: 20170613:130631 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]