Construction of Lightweight MDS Matrices over the Matrix Polynomial Residue Ring

Lijing Zhou; Licheng Wang; Yiru Sun

Paper 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.

Note: Publish the full version of my paper.

Metadata

Available format(s): PDF
Publication info: Preprint. MAJOR revision.
Keywords: MDS matrix XOR count matrix polynomial residue ring involutory matrix
Contact author(s): 379739494 @ qq com
History: 2017-06-13: last of 8 revisions; 2016-12-28: received; See all versions
Short URL: https://ia.cr/2016/1173
License: CC BY

BibTeX

@misc{cryptoeprint:2016/1173,
      author = {Lijing Zhou and Licheng Wang and Yiru Sun},
      title = {Construction of Lightweight {MDS} Matrices over the Matrix Polynomial Residue Ring},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/1173},
      year = {2016},
      url = {https://eprint.iacr.org/2016/1173}
}