Cryptology ePrint Archive: Report 2019/847
Improved Heuristics for Short Linear Programs
Quan Quan Tan and Thomas Peyrin
Abstract: In this article, we propose new heuristics for minimizing the amount of XOR gates required to compute a system of linear equations in GF(2). We first revisit the well known Boyar-Peralta strategy and argue that a proper randomization process during the selection phases can lead to great improvements. We then propose new selection criteria and explain their rationale. Our new methods outperform state-of-the-art algorithms such as Paar or Boyar-Peralta (or open synthesis tools such as Yosys) when tested on random matrices with various densities. They can be applied on matrices of reasonable sizes (up to about 32 x 32). Notably, we provide a new implementation record for the matrix underlying the MixColumns function of the AES block cipher, requiring only 94 XORs.
Category / Keywords: implementation / XOR gate, gate count, linear system, diffusion matrices
Original Publication (in the same form): IACR-CHES-2020
DOI: 10.13154/tches.v2020.i1.203-230
Date: received 20 Jul 2019, last revised 28 Jan 2020
Contact author: quanquan001 at e ntu edu sg, thomas peyrin at ntu edu sg
Available format(s): PDF | BibTeX Citation
Version: 20200128:070806 (All versions of this report)
Short URL: ia.cr/2019/847
[ Cryptology ePrint archive ]