4
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Why do you think it would be more suitable? or why do you consider it lighter ? $\endgroup$ – Ruggero Jan 15 '18 at 17:04
  • $\begingroup$ @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. $\endgroup$ – Amin235 Jan 15 '18 at 17:24
  • 1
    $\begingroup$ 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? $\endgroup$ – e-sushi Jan 16 '18 at 11:32
  • $\begingroup$ @e-sushi you right. I will edit the question to clarify what did I mean by suitable for software Implementation. thanks for your comment. $\endgroup$ – Amin235 Jan 16 '18 at 12:20
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks for your answer. Is it possible to ask you to address the GitHub code of SLP heuristics. $\endgroup$ – Amin235 Dec 22 '18 at 10:27
  • 1
    $\begingroup$ @Amin235 sure you can ask me about it, I guess you are talking about our implementation (that is github.com/pfasante/shorter_linear_slps_for_mds_matrices)? Not sure thou, if this is the right place or if the github repository is the better place. $\endgroup$ – asante Dec 22 '18 at 18:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.