**A New Approach for the Implementation of Binary Matrices Using SLP Applications**

*Mahdi Sajadieh and Mohsen Mousavi*

**Abstract: **In this paper, we propose a method for implementing binary matrices with low-cost XOR. 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. Also, we show that the implementation of an MDS matrix M is associated with the form of the binary matrix used to construct the binary form of M. In addition, we propose a heuristics algorithm to implement MDS matrices. The best result of this paper is the implementation of a 8 × 8 involutory MDS matrix over 8-bit words with 408 XOR gates. The Paar algorithm is used as an SLP application to obtain implementations of this paper.

**Category / Keywords: **implementation / Shortest Straight-Line Program, MDS matrix, Heuristics algorithm for SLP

**Date: **received 12 Jan 2020

**Contact author: **m mousavi at mut-es ac ir

**Available format(s): **PDF | BibTeX Citation

**Version: **20200113:102957 (All versions of this report)

**Short URL: **ia.cr/2020/032

[ Cryptology ePrint archive ]