Paper 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.