Exhaustive search for small dimension recursive MDS diffusion layers for block ciphers and hash functions

Abstract

This article presents a new algorithm to find MDS matrices that are well suited for use as a diffusion layer in lightweight block ciphers. Using an recursive construction, it is possible to obtain matrices with a very compact description. Classical field multiplications can also be replaced by simple F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sub> -linear transformations (combinations of XORs and shifts) which are much lighter. Using this algorithm, it was possible to design a 16×16 matrix on a 5-bit alphabet, yielding an efficient 80-bit diffusion layer with maximal branch number.