Paper 2017/371

On the Construction of Lightweight Orthogonal MDS Matrices

Lijing Zhou, Licheng Wang, and Yiru Sun

Abstract

In present paper, we investigate 4 problems. Firstly, it is known that, a matrix is MDS if and only if all sub-matrices of this matrix of degree from 1 to $n$ are full rank. In this paper, we propose a theorem that an orthogonal matrix is MDS if and only if all sub-matrices of this orthogonal matrix of degree from 1 to $\lfloor\frac{n}{2}\rfloor$ are full rank. With this theorem, calculation of constructing orthogonal MDS matrices is reduced largely. Secondly, Although it has been proven that the $2^d\times2^d$ circulant orthogonal matrix does not exist over the finite field, we discover that it also does not exist over a bigger set. Thirdly, previous algorithms have to continually change entries of the matrix to construct a lot of candidates. Unfortunately, in these candidates, only very few candidates are orthogonal matrices. With the matrix polynomial residue ring and the minimum polynomials of lightweight element-matrices, we propose an extremely efficient algorithm for constructing $4\times4$ circulant orthogonal MDS matrices. In this algorithm, every candidate must be an circulant orthogonal matrix. Finally, we use this algorithm to construct a lot of lightweight results, and some of them are constructed first time.

Note: Modify some typos.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
MDS matrixXOR countpolynomial residue ringorthogonal matrixcirculant matrix
Contact author(s)
379739494 @ qq com
History
2017-06-13: last of 2 revisions
2017-04-28: received
See all versions
Short URL
https://ia.cr/2017/371
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/371,
      author = {Lijing Zhou and Licheng Wang and Yiru Sun},
      title = {On the Construction of Lightweight Orthogonal MDS Matrices},
      howpublished = {Cryptology ePrint Archive, Paper 2017/371},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/371}},
      url = {https://eprint.iacr.org/2017/371}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.