Towards a general construction of recursive MDS diffusion layers

MDS matrices are of great importance in the design of block ciphers and hash functions. MDS matrices are not sparse and have a large description and thus induce costly implementation in software/hardware. To overcome this problem, in particular for applications in light-weight cryptography, it was proposed by Guo et al. to use recursive MDS matrices. A recursive MDS matrix is an MDS matrix which can be expressed as a power of some companion matrix. Following the work of Guo et al., some ad-hoc search techniques are proposed to find recursive MDS matrices which are suitable for hardware/software implementation. In another direction, coding theoretic techniques are used to directly construct recursive MDS matrices: Berger technique uses Gabidulin codes and Augot et al. technique uses shortened BCH codes. In this paper, we first characterize the polynomials that yield recursive MDS matrices in a more general setting. Based on this we provide three methods for obtaining such polynomials. Moreover, the recursive MDS matrices obtained using shortened BCH codes can also be obtained with our first method. In fact we get a larger set of polynomials than the method which uses shortened BCH codes. Our other methods appear similar to the method which uses Gabidulin codes. We get a new infinite class of recursive MDS matrices from one of the proposed methods. Although we propose three methods for the direct construction of recursive MDS matrices, our characterization results pave the way for new direct constructions.