Paper 2017/195

Design of Lightweight Linear Diffusion Layers from Near-MDS Matrices

Chaoyun Li and Qingju Wang

Abstract

Near-MDS matrices provide better trade-offs between security and efficiency compared to constructions based on MDS matrices, which are favored for hardware-oriented designs. We present new designs of lightweight linear diffusion layers by constructing lightweight near-MDS matrices. Firstly generic $n\times n$ near-MDS circulant matrices are found for $5\leq n \leq 9$. Secondly\,, the implementation cost of instantiations of the generic near-MDS matrices is examined. Surprisingly, for $n=7,8$, it turns out that some proposed near-MDS circulant matrices of order $n$ have the lowest XOR count among all near-MDS matrices of the same order. Further, for $n=5,6$, we present near-MDS matrices of order $n$ having the lowest XOR count as well. The proposed matrices, together with previous construction of order less than five, lead to solutions of $n\times n$ near-MDS matrices with the lowest XOR count over finite fields $\mathbb{F}_{2^m}$ for $2\leq n \leq 8$ and $4\leq m \leq 2048$. Moreover, we present some involutory near-MDS matrices of order $8$ constructed from Hadamard matrices. Lastly, the security of the proposed linear layers is studied by calculating lower bounds on the number of active S-boxes. It is shown that our linear layers with a well-chosen nonlinear layer can provide sufficient security against differential and linear cryptanalysis.

Note: Delete the redundant 'and' in the author names.