In this paper authors claim that $\{0,1\}$-matrices are almost-MDS (have branch number $n - 1$) on when $n$ is $2, 3,$ or $4$.

For example, how can this two matrices have the same branch number? $$\begin{pmatrix}0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0\end{pmatrix}$$

$$\begin{pmatrix}0&1&1&1&1\\ 1&0&1&1&1\\ 1&1&0&1&1\\ 1&1&1&0&1\\ 1&1&1&1&0\end{pmatrix}$$

Why branch number doesn't scale up with matrix size?

I'm math dummy. It seems to me that bigger (more 1s) should be better for diffusion. Is there simple logical plain English explanation?


1 Answer 1


From the article on page 5;

Theorem 1 Let $A:{GF(2^m)}^n \to {GF(2^m)}^n$ be an $n\times n \{0,1\}$-matrix over $GF(2^m)$. Then the branch number of $A$ is at most $\frac{2n+4}{3}$.

Let $A$ be the almost-MDS matrix. So its branch number is $n$. Using above theorem we have

$$n \leq \frac{2n+4}{3} $$ So $n=2,3$ or $4$.

The size of matrix is a tool for finding upper bound of branch number. The branch number of $n\times n$ matrix is at most $n+1$ and equality occur, when matrix be MDS.

Also matrix $A$ is MDS if determinant of all its sub matrices be not $0$.

  • $\begingroup$ But why? I would expect branch number n for almost-MDS matrx of any size. $\endgroup$
    – LightBit
    May 21, 2016 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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