# What is the meaning of weight in cryptography and how is it related to branch number?

I am trying to understand the mixcolumn design of AES. I read that the branch number is 5 and there was a definition that referred to weight of vectors. What is weight of a vector?

In cryptography, "weight" of a vector of bits is most often the Hamming weight, that is the number of non-zero bits in the vector. But in this AES context, that's most probably the "bundle weight" of a vector of bundles of bits (e.g. a vector of bytes), defined as the number of non-zero bundles.

In the AES context, the "(differential) (bundle) branch number" of a Boolean transformation with respect to a bundle partition, as defined by Joan Daemen and Vincent Rijmen in The Design of Rijndael (2002), section 9.3, is a measure of diffusion. It is defined as the minimum bundle weight of the XOR of two distinct input/output combinations of said transformation. For MixColumns, that's the minimum number of bytes that can change between two distinct input/output combinations (of a total of 32 bytes), or equivalently the minimum number of bytes in a non-zero input/output combination; which is 5.

This is consistent with the general definition of Hamming weight in coding theory, where, for a given symbol alphabet, the weight of a nonzero symbol is $1$ while the weight of the zero symbol is $0.$ The designers of AES used MDS codes over the finite field $GF(2^8)$ (which can be represented by binary vectors of length 8, i.e., the vector space $GF(2)^8$). This is a $[length=8,dimension=4,min.~distance=5]$ code and the minimum weight (same as minimum distance since the code is linear) is $5$. This minimum weight corresponds to the guarantee that there are at least 5 total nonzero bytes amongst the 4 input and 4 output bytes (the number of input bytes is the dimension of the code and the number of input+output bytes is the length) of the $\textsf{MixCols}$ mapping.

This answer further discusses the branch number.

Thanks for the many useful contributions in comments!

• I have seen branch number consistently defined as $B(\theta) = min(w_t(a) + w_t(\theta(a)))$ for nonzero 0 in the works of Joan Daemen and company – Ella Rose Feb 17 '17 at 19:38
• The weight for AES, e.g., is based on symbol weight where symbols are in $GF(2)^8,$ and any nonzero Vector in $GF(2)^8$ (any nonzero Byte if you like) has weight 1. This is because the MDS code used in mixing has the same alphabet. – kodlu Feb 17 '17 at 23:06
• @fgrieu you are right that the term is overloaded and carelessly used. – kodlu Feb 19 '17 at 21:27
• Note that the Hamming weight is defined as the number of nonzero symbols, which don't have to be bits. So Hamming weight also applies to $\mathbb{F}_2^8$ and the comment by @kodlu doesn't contradict with the term "Hamming weight". – Aleph Feb 20 '17 at 9:54