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 matrixXOR countmatrix polynomial residue ringinvolutory 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2016/1173}},
      url = {https://eprint.iacr.org/2016/1173}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.