Presentation of a Method for Implementing Binary Matrices and its Application in the Implementation of MDS Matrices

MDS matrices have a crucial role in the cryptography and coding theory. MDS matrices are used as the diffusion layer in cryptosystems as well as in the construction of linear codes with the maximum error correction capability. On the one hand, the entries of MDS matrices are elements of finite fields. On the other hand, it is a major issue to implement finite fields in the lightweight cryptography. Therefore, to use MDS matrices in the lightweight cryptography, these matrices are first converted to binary matrices and then implemented using heuristics algorithms. In this paper, a method to implement binary matrices with low-cost XOR is proposed and then using the proposed method, a heuristics algorithm for implementing MDS matrices is introduced. The structure of the proposed heuristics algorithm is based on the assumption that let A be a binary matrix (or the binary form of an MDS matrix). First, using a random-iterative method, we obtain a list S from a binary matrix A. Then, based on the list S, we construct a binary matrix B. Next, we find a relation between the implementations of A and B. In other words, using the implementation of the matrix B, we get a low-cost implementation for the matrix A. In the structure of the proposed heuristics algorithm, one of the familiar SLP algorithms called Paar is applied.