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?


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 '16 at 12:09

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.