A Lightweight Matrix Suggestion for MixColumns State of AES

Question

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.

Answer 1

I'm not sure to what paper you reference with "30th paper from FSE 2018" because in this list the 30. paper is not about implementing MDS matrices. As the 31. paper is, I assume you refer to this, entitled "Shorter Linear Straight-Line Programs for MDS matrices".

When you take the XOR count as a metric for efficiency, you can just compute this for your matrix and end up with an naive XOR count of 144, an optimized XOR count of 103 when using the SLP heuristics from the above paper. While the 144 XORs for the naive implementation are better than 152 XORs we would need for a naive implementation of the AES MC matrix, the later can also be optimized with SLPs and this will give you an implementation with only 97 XORs. So, when only using the XOR count metric, it appears that your matrix is not more efficient than the AES matrix.

Of course it also depends a lot what application you have, if you only need to encrypt stuff (e.g. using AES in CTR mode), looking only at the "normal" matrices is fine, but when you also need decryption and thus the inverse matrices, these have to be implemented as well.