Optimizing implementations of linear layers
In this paper, we propose a new heuristic algorithm to search efficient implementations (in terms of Xor count) of linear layers used in symmetric-key cryptography. It is observed that the implementation cost of an invertible matrix is related to its matrix decomposition if sequential-Xor (s-Xor) me...
| Main Authors: | , , , , |
|---|---|
| Other Authors: | |
| Format: | Journal Article |
| Language: | English |
| Published: |
2020
|
| Subjects: | |
| Online Access: | https://hdl.handle.net/10356/145106 |
| _version_ | 1811690874399096832 |
|---|---|
| author | Xiang, Zejun Zeng, Xiangyong Lin, Da Bao, Zhenzhen Zhang, Shasha |
| author2 | School of Physical and Mathematical Sciences |
| author_facet | School of Physical and Mathematical Sciences Xiang, Zejun Zeng, Xiangyong Lin, Da Bao, Zhenzhen Zhang, Shasha |
| author_sort | Xiang, Zejun |
| collection | NTU |
| description | In this paper, we propose a new heuristic algorithm to search efficient implementations (in terms of Xor count) of linear layers used in symmetric-key cryptography. It is observed that the implementation cost of an invertible matrix is related to its matrix decomposition if sequential-Xor (s-Xor) metric is considered, thus reducing the implementation cost is equivalent to constructing an optimized matrix decomposition. The basic idea of this work is to find various matrix decompositions for a given matrix and optimize those decompositions to pick the best implementation. In order to optimize matrix decompositions, we present several matrix multiplication rules over F2, which are proved to be very powerful in reducing the implementation cost. We illustrate this heuristic by searching implementations of several matrices proposed recently and matrices already used in block ciphers and Hash functions, and the results show that our heuristic performs equally good or outperforms Paar’s and Boyar-Peralta’s heuristics in most cases. |
| first_indexed | 2024-10-01T06:10:56Z |
| format | Journal Article |
| id | ntu-10356/145106 |
| institution | Nanyang Technological University |
| language | English |
| last_indexed | 2024-10-01T06:10:56Z |
| publishDate | 2020 |
| record_format | dspace |
| spelling | ntu-10356/1451062023-02-28T19:34:04Z Optimizing implementations of linear layers Xiang, Zejun Zeng, Xiangyong Lin, Da Bao, Zhenzhen Zhang, Shasha School of Physical and Mathematical Sciences Science::Mathematics Linear Layer Implementation In this paper, we propose a new heuristic algorithm to search efficient implementations (in terms of Xor count) of linear layers used in symmetric-key cryptography. It is observed that the implementation cost of an invertible matrix is related to its matrix decomposition if sequential-Xor (s-Xor) metric is considered, thus reducing the implementation cost is equivalent to constructing an optimized matrix decomposition. The basic idea of this work is to find various matrix decompositions for a given matrix and optimize those decompositions to pick the best implementation. In order to optimize matrix decompositions, we present several matrix multiplication rules over F2, which are proved to be very powerful in reducing the implementation cost. We illustrate this heuristic by searching implementations of several matrices proposed recently and matrices already used in block ciphers and Hash functions, and the results show that our heuristic performs equally good or outperforms Paar’s and Boyar-Peralta’s heuristics in most cases. Ministry of Education (MOE) Nanyang Technological University Published version Zhenzhen Bao was partially supported by Nanyang Technological University in Singapore under Grant 04INS000397C230, and Singapore’s Ministry of Education under Grants RG18/19 and MOE2019-T2-1-060. 2020-12-11T02:09:04Z 2020-12-11T02:09:04Z 2020 Journal Article Xiang, Z., Zeng, X., Lin, D., Bao, Z., & Zhang, S. (2020). Optimizing implementations of linear layers. IACR Transactions on Symmetric Cryptology, 2020(2), 120-145. doi:10.13154/tosc.v2020.i2.120-145 2519-173X https://hdl.handle.net/10356/145106 10.13154/tosc.v2020.i2.120-145 2 2020 120 145 en 04INS000397C23 RG18/19 MOE2019-T2-1-060 IACR Transactions on Symmetric Cryptology © 2020 Zejun Xiang, Xiangyoung Zeng, Da Lin, Zhenzhen Bao, Shasha Zhang. This work is licensed under a Creative Commons Attribution 4.0 International License. application/pdf |
| spellingShingle | Science::Mathematics Linear Layer Implementation Xiang, Zejun Zeng, Xiangyong Lin, Da Bao, Zhenzhen Zhang, Shasha Optimizing implementations of linear layers |
| title | Optimizing implementations of linear layers |
| title_full | Optimizing implementations of linear layers |
| title_fullStr | Optimizing implementations of linear layers |
| title_full_unstemmed | Optimizing implementations of linear layers |
| title_short | Optimizing implementations of linear layers |
| title_sort | optimizing implementations of linear layers |
| topic | Science::Mathematics Linear Layer Implementation |
| url | https://hdl.handle.net/10356/145106 |
| work_keys_str_mv | AT xiangzejun optimizingimplementationsoflinearlayers AT zengxiangyong optimizingimplementationsoflinearlayers AT linda optimizingimplementationsoflinearlayers AT baozhenzhen optimizingimplementationsoflinearlayers AT zhangshasha optimizingimplementationsoflinearlayers |