Can zero be one of the elements used in an MDS matrix (in the context of AES)?

Based on what I have read all entries of an MDS Matrix need to be non-zero. Also, I would appreciate any help in understanding the reason behind this requirement if zero cannot be an element of MDS.

  • $\begingroup$ In any MDS matrix, any square submatrix (subset of rows/columns) must be invertible. This includes 1x1 matrices. $\endgroup$ – Fractalice Nov 2 '20 at 8:45

No, for MDS codes used in the way it is used in AES there's no other choice, i.e., an MDS code with these dimension must have all entries nonzero in the $M$ matrix.

The MDS matrix $M$ has to be square, mapping 4 bytes to 4 bytes and must have 4 nonzero entries in each row by MDS property.

It also means changing each input byte affects each output byte, helping in diffusion.

Background: by coding theory the code is generated by the $k\times n$ matrix $$G=[I|M]$$ The Matrix converts a length $k$ message $m$ to the codeword $c$ via $$ c=mG $$ where $m,c$ are row vectors. This code has minimum weight $n-k+1$, the maximum possible by singleton bound. Since each row is a codeword the $M$ submatrix must have rows of minimum weight $n-k$. For AES, $n=2k=8$ so $n-k=4.$ So the rows of $M$ must have 4 nonzero entries.

  • $\begingroup$ Thank you @kodlu, really appreciate your help. $\endgroup$ – X_Novichok_X Nov 2 '20 at 3:45
  • $\begingroup$ ok, you can upvote the answer :-) $\endgroup$ – kodlu Nov 2 '20 at 3:49
  • $\begingroup$ I tried doing that but the platform does not allow me unfortunately. Here is the message I keep getting: "Thanks for the feedback! Votes cast by those with less than 15 reputation are recorded, but do not change the publicly displayed post score." $\endgroup$ – X_Novichok_X Nov 2 '20 at 3:58
  • $\begingroup$ @kodlu what do you mean by "no other choice"? $\endgroup$ – Fractalice Nov 2 '20 at 8:45
  • $\begingroup$ @kodlu could you take the advantage of the title to write this answer for beginners? $\endgroup$ – kelalaka Nov 2 '20 at 10:42

After digging deeper here is what I found:

Let M be an MDS matrix, for any square sub-matrix Mi,j of M. From the property of MDS matrices, every sub-matrix should be non-singular.

No Mi,j elements belonging to M can be equal to zero, since this would lead to a singular submatrix of type 1×1 in M and thus would contradict the non-singularity requirement.

Simply put the cofactor matrix cannot be zero for a 1x1 sub-matrix of M if M is MDS since every sub-matrix of M should be non-singular (invertible).



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.