A Framework to Optimize Implementations of Matrices

In this paper, we propose several reduction rules to optimize the given implementation of a binary matrix over \(\mathbb {F}_{2}\). Moreover, we design a top-layer framework which can make use of the existing search algorithms for solving SLP problems as well as our proposed reduction rules. Thus, efficient implementations of matrices with fewer Xor gates can be expected with the framework. Our framework outperforms algorithms such as Paar1, RPaar1, BP, BFI, RNBP, A1 and A2 when tested on random matrices with various densities and those matrices designed in recent literature. Notably, we find an implementation of AES MixColumns using only 91 Xors, which is currently the shortest implementation to the best of our knowledge.