Let $$M= \begin{bmatrix}0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0\end{bmatrix}$$ which is used in the block ciphers MIDORI and MANTIS. Of course this matrix is optimal in terms of hardware area since it uses 0 and 1. However, is there a 4 by 4 MDS matrix which can prove to be better than the one used in MIDORI in some sense? Will it be futile to search for such a class of matrices?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
1
Let us consider "bricklayer" designs such as AES, MIDORI, SKINNY and MANTIS where such matrices are used to "mix columns" of 4 4-bit or 8-bit cells which make up the state. The weight formulae for a binary MDS code show that $M$ is indeed the best possible binary matrix and gives the branch number of 4 on cells.
Note however that the AES MixCol matrix achieves a branching number of 5 on cells, which is superior diffusion in some sense. It is able to do this using a MDS matrix over $\mathbb F_{256}$ rather than $\mathbb F_2$.
Moreover, if we look at the bit level, with $M$ there is no mixing between the bit levels of cells and the branch number is still 4. With AES, bit levels are mixed and a single output bit will depend on at least 5 input bits giving a bit-level branch number of 6. The importance of bit level branching is less of a concern than cell level branching provided that the $S$-boxes in the design provide good mixing. However, if there were linear or difference properties of the $S$-box that used only a subset of bit levels, $M$ would allow paths such that the content of the unused bit levels are irrelevant to the distinguisher.
Conversely, we can consider matrices with worse branching number, but with more efficient implementation than $M$ due to sparseness. This is the choice in SKINNY where the matrix
$$\begin{bmatrix}1&0&1&1\\ 1&0&0&0\\ 0&1&1&0\\ 1&0&1&0\end{bmatrix}$$
is used and the minimal branching number of 2 is accepted (better branching is achieved over multiple rounds).