International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Improved Heuristics for Short Linear Programs

Authors:
Quan Quan Tan , Nanyang Technological University, Singapore
Thomas Peyrin , Nanyang Technological University, Singapore
Download:
DOI: 10.13154/tches.v2020.i1.203-230
URL: https://tches.iacr.org/index.php/TCHES/article/view/8398
Search ePrint
Search Google
Presentation: Slides
Abstract: 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.
Video from TCHES 2019
BibTeX
@article{tches-2019-29960,
  title={Improved Heuristics for Short Linear Programs},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universit├Ąt Bochum},
  volume={2020, Issue 1},
  pages={203-230},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8398},
  doi={10.13154/tches.v2020.i1.203-230},
  author={Quan Quan Tan and Thomas Peyrin},
  year=2019
}