# A Lightweight Matrix Suggestion for MixColumns State of AES

We know that the matrix in the MixColumns state of AES is the circulant MDS matrix $$C=circ(2,3,1,1)$$ which is defined over $$GF(2^8)$$ with the irreducible polynomial $$f=x^{8}+x^{4}+x^{3}+x+1$$. Let we show the elements of $$GF(2^8)$$ with positive integer numbers. For example, when we assume that the elements $$2$$, $$3$$ and $$4$$, we mean $$\alpha$$, $$\alpha+1$$and $$\alpha^2$$ where $$\alpha$$ is a root of $$f$$. Consider the following matrix over $$GF(2^8)$$ $$A= \left( \begin {array}{cccc} 2&1&1&1\\ 1&1&3&2\\ 1&3&4&1\\ 1&2&1&3 \end {array} \right)$$ All squarer sub-matrices of $$A$$ are non-singular or in the other words $$A$$ is an MDS(super-regular) matrix over $$GF(2^8)$$.

My question: Is matrix $$A$$ is suitable for software Implementation rather than $$C$$?

Edit:(Motivated by @Richie Frame comment) The inverse of $$A$$, denoted with $$A^{-1}$$, looks like to semi-circulant matrix as shown $$A^{-1}= \left( \begin {array}{cccc} 11&194&120&173\\ 194&57&173&11\\ 120&173&111&50\\ 173&11&50&120 \end {array} \right)$$ Although $$A^{-1}$$ is consist of seven elements $$(11, 50,57,111, 120, 173, 194)$$, from two elements $$11$$ and $$50$$ we can obtain other elements as follows $$\left\{ \begin {array}{lcr} 11+50&=&57, \\ 11+50^2 &=& 120, \\ 11^2+50^5 &=& 173, \\ 11^8+50^8 &=& 194 ,\\ 173+194&=&111. \end {array} \right.$$

Edit:(Motivated by @e-sushi comment) After Definition 5 of the second paper, we have

For an efficient implementation of the perfect diffusion layer, it is desirable to have maximum number of 1’s and minimum number of different entries in the MDS matrix.

Although based on the this terminology $$C$$ has an efficient implementation rather than $$A$$, I want to see this one by terminology of XOR and xtime.

After Proposition 3 of the second paper, the authors proved that multiplication by the matrix of AES can be implemented using $$15$$ XORs, $$4$$ xtimes (or $$4$$ table lookups) and $$3$$ temporary variables.

Unfortunately I do not know how to obtain XOR and xtime when the matrix $$A$$ is applied in MixColumns state of AES.

In addition, I used software Implementation expression in the question since the matrix of AES($$C$$) is a circulant matrix, but the matrix $$A$$ is not circulant and in 31th paper of FSE 2018, it is claimed that

using a circulant matrix gives adequate flexibility to do a trade-off between the area requirement and clock cycle, whereas most of the other matrix types are suitable for either one but not both circumstances.

• Why do you think it would be more suitable? or why do you consider it lighter ? – Ruggero Jan 15 '18 at 17:04
• @Ruggero Please see Section 3 of this paper or Section 2 of this paper. The second paper explained more clearly the concept of lighter in construction of MDS matrices. – Amin235 Jan 15 '18 at 17:24
• Is matrix A is suitable for software Implementation rather than C? – Depending on how you implement things, “lighter” as mentioned in those papers does not directly translate to “more suitable” when talking about implemetation. Related to that terminology: Can you please define what exactly you mean with “more suitable for software Implementation”? In what way? – e-sushi Jan 16 '18 at 11:32
• @e-sushi you right. I will edit the question to clarify what did I mean by suitable for software Implementation. thanks for your comment. – Amin235 Jan 16 '18 at 12:20