2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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$. $\endgroup$ – Samuel Neves Sep 17 at 0:25
  • $\begingroup$ 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$? $\endgroup$ – hola Sep 17 at 9:29
  • 1
    $\begingroup$ Section 2 of Design of Block Ciphers and Coding Theory, for example. $\endgroup$ – Samuel Neves Sep 18 at 9:06
  • 1
    $\begingroup$ Read this paper carefully. For example, please see the binary matrices in Page 14 to find your answer. $\endgroup$ – user0410 Sep 25 at 14:36
  • $\begingroup$ @user0410 Okay... They seem to give some examples. The formulation of binary -- MDS in not clear though. $\endgroup$ – hola Sep 25 at 15:51
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Wow! That is insightful. Thanks. $\endgroup$ – hola Sep 28 at 8:18
  • $\begingroup$ Your welcome dear. $\endgroup$ – user0410 Sep 28 at 11:19

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.