Improved Heuristics for Short Linear Programs

  • Quan Quan Tan Nanyang Technological University, Singapore
  • Thomas Peyrin Nanyang Technological University, Singapore
Keywords: XOR gate, gate count, linear systems, diffusion matrices


In this article, we propose new heuristics for minimising 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 randomisation 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 to matrices of reasonable sizes (up to about 32 × 32). Notably, we provide a new implementation record for the matrix underlying the MixColumns function of the AES block cipher, requiring only 94 XORs.

How to Cite
Tan, Q. Q., & Peyrin, T. (2019). Improved Heuristics for Short Linear Programs. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(1), 203-230.