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.

Available format(s)
Category
Implementation
Publication info
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
See all versions
Short URL
https://ia.cr/2019/847

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},
note = {\url{https://eprint.iacr.org/2019/847}},
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.