Open AccessImproved Heuristics for Short Linear Programs
Author(s) -
Quan Quan Tan,
Thomas Peyrin
Publication year - 2019
Publication title -
iacr transactions on cryptographic hardware and embedded systems
Language(s) - English
Resource type - Journals
ISSN - 2569-2925
DOI - 10.46586/tches.v2020.i1.203-230
Subject(s) - heuristics , selection (genetic algorithm) , computer science , matrix (chemical analysis) , block (permutation group theory) , mathematical optimization , process (computing) , theoretical computer science , algorithm , mathematics , artificial intelligence , programming language , combinatorics , materials science , composite material
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.