A few negative results on constructions of MDS matrices using low XOR matrices

Abstract

This paper studies some low XOR matrices systematically. Some known low XOR matrices are companion, DSI and sparse DSI matrices. Companion matrices have been well studied now whereas DSI and sparse DSI are newly proposed matrices. There are very few results on these matrices. This paper presents some new mathematical results and rediscovers some existing results on DSI and sparse DSI matrices. Furthermore, we start from a matrix with the minimum number of fixed XORs required, which is one, to construct any recursive MDS matrix. We call such matrices 1-XOR matrices. No family of low XOR matrices can have lesser fixed XORs than 1-XOR matrices. We then move on to 2-XOR and provide some impossibility results for matrices of order 5 and 6 to compute recursive MDS matrices. Finally, this paper shows the non-existence of 8-MDS sparse DSI matrix of order 8 over the field F28. © Springer Nature Switzerland AG 2019.