# Prove the branch of number of Advanced Encryption Standard

In the Advanced Encryption Standard (AES) document: page 27 section 7.3.1, It defines branch number. It said

" Let F be a linear transformation acting on byte vectors and let the byte weight of a vector be the number of nonzero bytes. The byte weight of a vector is denoted by $W(a)$.

Definition: The branch number of a linear transformation $F$ is $$min_{a\neq0}(W(a) + W(F(a)))$$

If the branch number is 5, a difference in 1 input (or output) byte propagates to all 4 output (or input) bytes, a 2-byte input (or output) difference to at least 3 output (or input) bytes. Moreover, a linear relation between input and output bits involves bits from at least 5 different bytes from input and output."

The AES chose polynomial $c(x)=03x^3+01x^2+01x+02$ to construct MixColumn operation , where the coefficients are hexadecimal representation of numbers in $GF_{256}$(e.g. $03_{hexadecimal}= 0000 0011_{binary} =\alpha+1_{polynomial\,representation}$) The MixColumn operation is done by multiplying $c(x)$ and mod $x^4+1$

However, the document doest not give a mathematical proof. My questions are

1. Prove the maximum branch number is $5$. Besides, AES MixColumn can achieve the maximum value as $5$.
2. given a branch number, how to construct the linear transforamtion $F(\,)$ (in the case of AES, it is $5$) ?
3. Reversely, given $F$ (a matrix), how to estimate its branch number?
For example, how should I prove that if the linear transformation is self-inverse
($\;(c(x))^2\equiv 1 \;mod\,x^4+1$ or $F^2=I$ ), then the branch number is at most $4$?

I suppose these problems are related to matrix norm, but I do not know where to start to tackle these problems.

• Correction: idempotent means "doing it twice is the same as doing it once", that is a function $f$ is idempotent iff $f(f(x)) = f(x)$. What they mean is "self-inverse". – poncho May 3 '17 at 19:11
• It is self -inverse indeed. I had edited this post. Thank you for correction. – Rikeijin May 3 '17 at 19:29
• Possible duplicate of two questions.crypto.stackexchange.com/questions/42764/… and crypto.stackexchange.com/questions/35073/… – kodlu May 4 '17 at 3:26

The dear user @kodlu has answered to the similar question with excellent discussion but I want to answer with linear algebra argument.

We have two definitions for MDS (Maximum Distance Separable) Matrix:

First definition: A matrix $M$ of order $n$ is an MDS matrix if and only if every sub-matrix of $M$ is non-singular.

Second definition: A matrix $M_{n\times n}$ is MDS if and only if

$$Y_{n\times 1}=M_{n \times n}\, X_{n \times 1} \Longrightarrow \mathop{\rm min}_{X\neq 0}(W(Y)+W(X))=n+1$$

where $X={[x_0,x_1,\cdots , x_{n-1}]}^T$ and $Y={[y_0,y_1,\cdots , y_{n-1}]}^T$ are vectors in an arbitrary field and $W(X)$ is the number of non-zero elements of $X$.

Now, suppose that we use a MDS matrix( by first definition) of order $4$ and we want to proof by second definition that it's branch number is 5. Consider our MDS matrix be as follows

$$M=\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right]$$ the entries $m_{i,j}$ are non-zero because $M$ by first definition is MDS. Now consider the following equation $$MX=Y \Longrightarrow \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\\x_{{2}} \\ x_{{3}}\\ x_{{4}}\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\\ y_{{2}} \\ y_{{3}}\\ y_{{4}}\end {array} \right]$$ where $x_i$'s and $y_i$'s are elements of finite field. By second definition $X$ should be non-zero. For simplicity, consider $x_1\neq0$ and other $x_i$ can be zero or non-zero.

We should consider some cases to show that for every selection of $x_2$, $x_3$ and $x_4$, at least four elements of $x_2,x_3,x_4,y_1,y_2,y_3,y_4$ are non-zero.

The first case is $x_2=x_3=x_4=0$. in this case we have:

$$\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\\0 \\ 0\\ 0\end {array} \right]= \left[ \begin {array}{c} x_1\,m_{1,1}\\ x_1\,m_{2,1} \\ x_1\,m_{3,1}\\ x_1\,m_{4,1}\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\\ y_{{2}} \\ y_{{3}}\\ y_{{4}}\end {array} \right]$$ because $m_{i,j}$'s and $x_1$ are nonzero then the elements $y_1,y_2,y_3,y_4$ are nonzero. The next case is that are there non-zero values for $x_2,x_3,x_4$ such that

$$\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\\x_{{2}} \\ x_{{3}}\\ x_{{4}}\end {array} \right]= \left[ \begin {array}{c} 0\\ 0 \\ 0\\ 0\end {array} \right]$$ due to the $M$ matrix is non-singular we can conclude that $$\left[ \begin {array}{c} x_{{1}}\\x_{{2}} \\ x_{{3}}\\ x_{{4}}\end {array} \right]= \left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right]^{-1}\left[ \begin {array}{c} 0\\ 0 \\ 0\\ 0\end {array} \right]=\left[ \begin {array}{c} 0\\ 0 \\ 0\\ 0\end {array} \right]$$ and it contradict to our assumption that $x_1,x_2,x_3,x_4\neq 0$ and so one of the $y_1,y_2,y_3,y_4$ should be non-zero.

The next case is that: are there for example $x_1\neq0, x_2\neq0 ,x_3=x_4=0$ that result $y_1\neq0, y_2\neq0 ,y_3=y_4=0$. Consider there was this case as follows

$$\left[ \begin {array}{cccc} m_{{1,1}}&m_{{1,2}}&m_{{1,3}}&m_{{1,4}} \\ m_{{2,1}}&m_{{2,2}}&m_{{2,3}}&m_{{2,4}} \\ m_{{3,1}}&m_{{3,2}}&m_{{3,3}}&m_{{3,4}} \\ m_{{4,1}}&m_{{4,2}}&m_{{4,3}}&m_{{4,4}} \end {array} \right] \left[ \begin {array}{c} x_{{1}}\\x_2 \\ 0\\ 0\end {array} \right]= \left[ \begin {array}{c} y_{{1}}\\ y_{{2}} \\ 0\\ 0\end {array} \right]$$ so we have $$\left[ \begin {array}{cc} m_{{3,1}}&m_{{3,2}}\\ m_{ {4,1}}&m_{{4,2}}\end {array} \right] \left[ \begin {array}{c} x_{{1}}\\ x_{{2}} \end {array} \right]= \left[ \begin {array}{c} 0\\ 0\end {array} \right]$$ from the first definition all sub-matrix of $M$ has non-zero determinant and hence we can conclude from the above equation that the values of $x_1=x_2=0$ and it contradict to our assumption.

The other cases are similar to mentioned cases and use from this fact that all sub-matrix of $M$ have non-zero determinant.

I hope you find it useful.