Improved Heuristics for Short Linear Programs
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2019-11-01
|
| Series: | Transactions on Cryptographic Hardware and Embedded Systems |
| Subjects: | |
| Online Access: | https://tches.iacr.org/index.php/TCHES/article/view/8398 |
| _version_ | 1811317246295801856 |
|---|---|
| author | Quan Quan Tan Thomas Peyrin |
| author_facet | Quan Quan Tan Thomas Peyrin |
| author_sort | Quan Quan Tan |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-13T12:03:27Z |
| format | Article |
| id | doaj.art-1c6fa5d254f24a56ae4c424aa785465e |
| institution | Directory Open Access Journal |
| issn | 2569-2925 |
| language | English |
| last_indexed | 2024-04-13T12:03:27Z |
| publishDate | 2019-11-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | Transactions on Cryptographic Hardware and Embedded Systems |
| spelling | doaj.art-1c6fa5d254f24a56ae4c424aa785465e2022-12-22T02:47:42ZengRuhr-Universität BochumTransactions on Cryptographic Hardware and Embedded Systems2569-29252019-11-012020110.13154/tches.v2020.i1.203-230Improved Heuristics for Short Linear ProgramsQuan Quan Tan0Thomas Peyrin1Nanyang Technological University, SingaporeNanyang Technological University, SingaporeIn 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.https://tches.iacr.org/index.php/TCHES/article/view/8398XOR gategate countlinear systemsdiffusion matrices |
| spellingShingle | Quan Quan Tan Thomas Peyrin Improved Heuristics for Short Linear Programs Transactions on Cryptographic Hardware and Embedded Systems XOR gate gate count linear systems diffusion matrices |
| title | Improved Heuristics for Short Linear Programs |
| title_full | Improved Heuristics for Short Linear Programs |
| title_fullStr | Improved Heuristics for Short Linear Programs |
| title_full_unstemmed | Improved Heuristics for Short Linear Programs |
| title_short | Improved Heuristics for Short Linear Programs |
| title_sort | improved heuristics for short linear programs |
| topic | XOR gate gate count linear systems diffusion matrices |
| url | https://tches.iacr.org/index.php/TCHES/article/view/8398 |
| work_keys_str_mv | AT quanquantan improvedheuristicsforshortlinearprograms AT thomaspeyrin improvedheuristicsforshortlinearprograms |