# How to check that an $km \times km$ block-binary matrix is an MDS matrix in $k$-bit words over $\operatorname{GF}(2)$

I have been reading about MDS matrices. It is defined as (paraphrased from Section 2.1)

An $$n \times n$$ matrix $$M$$ is MDS if and only if $$bn(M) = n + 1$$ where $$bn$$ (branch number) is defined as: $$bn(M) = \min_{u\neq0}({hw(u) + hw(Mu)})$$ where $$hw$$ denotes Hamming weight.

It seems the MDS matrices like that of AES are defined over higher order fields like $$\operatorname{GF}(2^8)$$. It also seems the AES MDS matrix can be written as a matrix over $$\operatorname{GF}(2)$$. See this for example.

My question is, how does the MDS property translate to a binary matrix? Say, I am given an $$n\times n$$ binary invertible matrix, how can I understand whether this matrix is MDS or not?

I found some discussion in Section 2.1 about binary MDS matrices though, but could not get the idea.

• MDS matrices over $\mathbb{F}_2$ do not, in general, exist. For example, for $8\times 8$ binary matrices the maximum branch number is $5$, not $9$; for $16\times 16$ matrices it's $8$, not $17$. – Samuel Neves Sep 17 '20 at 0:25
• I see. Do you have a referecne for this, I mean the proof that, for $8\times8$ binary matrices the maximum branch number is $5$? – hola Sep 17 '20 at 9:29
• Section 2 of Design of Block Ciphers and Coding Theory, for example. – Samuel Neves Sep 18 '20 at 9:06
• Read this paper carefully. For example, please see the binary matrices in Page 14 to find your answer. – user0410 Sep 25 '20 at 14:36
• @user0410 Okay... They seem to give some examples. The formulation of binary -- MDS in not clear though. – hola Sep 25 '20 at 15:51

## 1 Answer

Let $$\bf A$$ be an $$n \times n$$ binary matrix. Let we want to check that whether $$\bf A$$ is an MDS matrix over the finite field $$\mathbb{F}_{2^k}$$ for some $$k$$?

The necessary condition is that $$k\mid n$$ which means $$n=km$$ for some integer $$m$$.

Now Let $$\bf A$$ be $$km \times km$$ binary matrix. The first step is that to consider the matrix $$\bf A$$ as a block binary matrix as follows where $${\bf B}_{i,j}$$, $$1\leq i,j \leq m$$ are $$k \times k$$ binary matrices. $${\bf A}= \left( \begin{array}{c|c|c|c} {\bf B}_{1,1} & {\bf B}_{1,2} & \cdots & {\bf B}_{1,m} \\ \hline {\bf B}_{2,1} & {\bf B}_{2,2} & \cdots & {\bf B}_{2,m} \\\hline \vdots & \vdots & \cdots & \vdots \\\hline {\bf B}_{m,1} & {\bf B}_{m,2} & \cdots & {\bf B}_{m,m} \end{array} \right).$$ Next, we should consider all square sub-matrices of the block matrix $$\bf A$$ and check that whether these sub-matrices are non-singular over $$\mathbb{F}_2$$? For example one of the square sub-matrices of $$\bf A$$ is as follows. The matrix $$\bf C$$ is an $$2k \times 2k$$ binary matrix and we should check its singularity over $$\mathbb{F}_2$$. $${\bf C}= \left( \begin{array}{} {\bf B}_{1,1} & {\bf B}_{1,2} \\ {\bf B}_{2,1} & {\bf B}_{2,2}. \end{array} \right).$$

Note that if all square sub matrices of the block matrix $$\bf A$$ are non-singular over $$\mathbb{F}_2$$, then we say $$\bf A$$ is an MDS matrix over $$k$$-bit inputs or $$k$$-bit words.

Maybe you ask this question: Is $$\bf A$$ an MDS matrix over $$\mathbb{F}_{2^k}$$ for some irreducible polynomial of degree $$k$$ over $$\mathbb{F}_2$$? The answer is yes when $$\bf A$$ is obtained from an $$m \times m$$ matrix such as $$\bf M$$ provided that the entries of $$\bf M$$ belong to $$\mathbb{F}_{2^k}$$. Let me make an example to learn it more clearly.

Consider the following $$4\times 4$$ matrix where the entries of $$\bf M$$ belong $$\mathbb{F}_{2^8}$$ such that this finite field is constructed from the irreducible polynomial $$f(x)={x}^{8}+{x}^{4}+{x}^{3}+x+1$$ over $$\mathbb{F}_2$$ (some users of this forum maybe say it is the MDS matrix of AES, but imagine we do not know this fact and we want to check it!).

$$\scriptsize{ {\bf M}= \left( \begin {array}{cccc} \alpha&\alpha+1&1&1\\ 1&\alpha&\alpha+1&1\\ 1&1&\alpha&\alpha+1\\ \alpha+1&1&1&\alpha \end {array} \right).}$$

Now we obtain a $$8 \times 8$$ binary matrix such that its characteristic polynomial over $$\mathbb{F}_2$$ is equal to $$f(x)$$ such as the following one $$\scriptsize{ {\bf N}= \left( \begin {array}{cccccccc} 0&0&0&0&0&1&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&0&0&0&1&0\\ 1&0&0&0&0&0&1&0\\ 0&1&0&0&0&0&0&1\\ 0&1&0&0&0&0&0&0\\ 0&0&0&1&0&0&0&0\\ 1&0&1&0&0&0&0&0 \end {array} \right).}$$ Next, by applying $$\bf N$$ we transform $$\bf M$$ to a $$32 \times 32$$ binary matrix, denoted $$\bf A$$, as follows. Let the $$(i,j)$$ entry of $$\bf M$$ be $$\sum_{i=0}^{7}b_i\alpha^i$$ where $$b_i$$'s are binary numbers. Now the $$(i,j)$$ entry of the block matrix $$\bf A$$ is equal to $$\sum_{i=0}^{7}b_i{\bf N}^i$$ in modulo 2. Therefore, the block matrix $$\bf A$$ is given by $$\scriptsize{ \left( \begin {array}{cccccccc|cccccccc|cccccccc|cccccccc} 0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0\\ 0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0\\ 0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0\\ 1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0\\ 0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0\\ 0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\ 0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0\\ 1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1\\ \hline 1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0\\ 0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0\\ 0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0\\ 0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0\\ 0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0\\ 0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0\\ 0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0\\ 0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1\\ \hline 1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0&1&0&0&0&0&1&0&0\\ 0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&1&0&0&0\\ 0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&1&0\\ 0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1&0\\ 0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0&1&0&0&1&0&0&1\\ 0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0\\ 0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&1&0\\ 0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0&1&0&1&0&0&0&0&1\\ \hline 1&0&0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&0&1&0&0\\ 0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&1&0&0&0\\ 0&0&1&0&0&0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&0&0&0&0&1&0\\ 1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1&0\\ 0&1&0&0&1&0&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0&0&1\\ 0&1&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&1&0&0&0&0&0&0\\ 0&0&0&1&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&1&0&0&0&0\\ 1&0&1&0&0&0&0&1&0&0&0&0&0&0&0&1&0&0&0&0&0&0&0&1&1&0&1&0&0&0&0&0 \end {array} \right).}$$

The final step is that we check the singularity of all square sub-matrices of the block matrix $$\bf A$$ over $$\mathbb{F}_2$$ (the number of these sub-matrices are $${2n\choose n}-1$$, for example for AES is 69).

Maybe you ask this question what is the advantages of this scenario. One answer is that the computation over $$\mathbb{F}_2$$ is more faster than the finite fields.

I hope you find this answer helpful.

• Wow! That is insightful. Thanks. – hola Sep 28 '20 at 8:18
• Your welcome dear. – user0410 Sep 28 '20 at 11:19