1. PLA Information Engineering University, Zhengzhou 450001, China
2. State Key Laboratory of Mathematical Engineering and Advanced Computing, Zhengzhou 450001, China
Compared with maximal distance separable (MDS) matrices, near-MDS matrices offer better tradeoff between security and efficiency, so it is more widely used in hardware-oriented lightweight cryptographic algorithm design under the resource-constrained environments. The number of XORs (XOR operations) describes the efficiency of the hardware implementation. This paper presents a new hardware-oriented lightweight near-MDS matrices construction algorithm, to construct the near-MDS matrices with as few XORs as possible. The key point of this paper is to construct near-MDS matrices by using the matrix in the GL(m, F2), m=4,8 (m*m matrices set on the binary field, m represents the number of bits in the S box) as an element of the diffusion matrix, this method is used to construct a 4*4 cyclic involution near-MDS matrix with the least number of XOR operations compared with the previous results. This paper uses the properties of special matrices to give a conditional lemma among the elements of the diffusion matrix of the cyclic involution form, and use it as a constraint condition for the searching algorithm to reduce the computational complexity. Combining the properties of the near-MDS matrix itself, the Matlab software is used to search the matrix that satisfies the constrained condition. It takes about 6 minutes in a Windows 10 system, i5-6200U CPU processor and 4 G memory. 48 cyclic involution near-MDS matrices are found that meet the conditions when m=4, with 10 more best results than in the existing results. When m=8, some cyclic involution near-MDS matrices that reach the lower bound of XORs are also given with the ``subfield construction'' method. And the time complexity of searching is decreased.