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

**Category / Keywords: **MDS matrix, XOR count, polynomial residue ring, orthogonal matrix, circulant matrix

**Date: **received 25 Apr 2017, last revised 13 Jun 2017

**Contact author: **379739494 at qq com

**Available format(s): **PDF | BibTeX Citation

**Note: **Modify some typos.

**Version: **20170613:082332 (All versions of this report)

**Short URL: **ia.cr/2017/371

[ Cryptology ePrint archive ]