CIRCULANT, CIRCULANT-LIKE AND ORTHOGONAL MDS GENERALIZED CAUCHY MATRICES

A matrix M over the filed F-q is called maximum distance separable (MDS) if all of its square submatrices are invertible. MDS generalized Cauchy (MDS-GC) matrices are important in both cryptography and coding theory. As an application, these matrices are used to provide diffusion in block ciphers. In this paper MDS-GC matrices over F-2k are constructed which are involutory, Hadamard, circulant or orthogonal. The construction is based on using linearly related Vandermonde matrices. First, the construction of nxn circulant MDS-GC matrices over F-2k is given for n a divisor of 2(k)-1; and an nxn circulant MDS-GC matrix C and its inverse C-1 are used to obtain the n x 2n matrix H = (C vertical bar vertical bar C-1) with square nonsingular submatrices. A class of 2(m) x 2(m) orthogonal MDS-GC matrices over F-2k is given subject to the divisibility of 2(k) - 1 by 2(m)-1. These orthogonal MDS-GC matrices are used to construct a new class of multiple MDS matrices over F-2k which have applications in the design of Feistel ciphers. The constructed n x n circulant matrices are also used to obtain (n + 1) x (n + 1) circulant-like MDS matrices over F-2k, and a closed-form expression for the inverse of these matrices is given. This is the first construction of circulant-like MDS matrices and their inverses which does not employ exhaustive search.