I'm reading an article about authenticated encryption algorithm - PAEQ.
It uses a permutation function AESQ, which has transormations from AES. And there is written about MegaSBoxes, which contain 4 rounds of AES transformation. So, there are 1 active MegaSBox in 4 rounds and 5 active MegaSBox in 8 rounds (because of branch number - 5).
So, the question is what is a branch number and why there are 5 MegaSBoxes, not 2?
More info in this paper (section 3.2.3, after lemma 3).
In AES, the MixColumns transform as a branch number of 5, this is because a change to a single byte input causes 4 of the output bytes to change. Like branches of a tree, 1+4=5. This is because MixColumns uses an MDS matrix for multiplications against the input.
AESQ operates on entire 128-bit blocks, which are further broken down into AES round operations. 2 AES round operations create full diffusion of the 128-bit block, so a single AESQ round consists of 2 AES rounds, in 4 parallel paths, followed by a shuffle operation so that 4 bytes from every AES round group go to a different group for the next round. What I am callling an AESQ round here is the output of a shuffle to the next shuffled output, I believe they call this 2 rounds in the paper.
Because the 2 AES rounds offer full diffusion, the branching of AESQ is a change 1 AES input block resulting in a change to 4 bytes of each AES output block. I color coded the blocks to show the distribution of modified bytes due to a change in any input byte over a single AESQ round (built from 8 AES rounds).
Therefore, just like in AES, we need 2 AESQ rounds for full diffusion of a single bit change to the the 512-input. This involves 16 AES rounds and 2 shuffle operations. This is considered MegaMixColumns plus MegaSubBytes, with a branch number of 5. This is called 4 rounds in the paper.
