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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published by the IACR in TCHES 2020
DOI
10.13154/tches.v2020.i1.203-230
Keywords
XOR gategate countlinear systemdiffusion matrices
Contact author(s)
quanquan001 @ e ntu edu sg
thomas peyrin @ ntu edu sg
History
2020-01-28: revised
2019-07-22: received
See all versions
Short URL
https://ia.cr/2019/847
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/847,
      author = {Quan Quan Tan and Thomas Peyrin},
      title = {Improved Heuristics for Short Linear Programs},
      howpublished = {Cryptology {ePrint} Archive, Paper 2019/847},
      year = {2019},
      doi = {10.13154/tches.v2020.i1.203-230},
      url = {https://eprint.iacr.org/2019/847}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.