Towards Low-Latency Implementation of Linear Layers
Lightweight cryptography features a small footprint and/or low computational complexity. Low-cost implementations of linear layers usually play an important role in lightweight cryptography. Although it has been shown by Boyar et al. that finding the optimal implementation of a linear layer is a Sh...
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2022-03-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/9532 |
| _version_ | 1818284776082112512 |
|---|---|
| author | Qun Liu Weijia Wang Yanhong Fan Lixuan Wu Ling Sun Meiqin Wang |
| author_facet | Qun Liu Weijia Wang Yanhong Fan Lixuan Wu Ling Sun Meiqin Wang |
| author_sort | Qun Liu |
| collection | DOAJ |
| description |
Lightweight cryptography features a small footprint and/or low computational complexity. Low-cost implementations of linear layers usually play an important role in lightweight cryptography. Although it has been shown by Boyar et al. that finding the optimal implementation of a linear layer is a Shortest Linear Program (SLP) problem and NP-hard, there exist a variety of heuristic methods to search for near-optimal solutions. This paper considers the low-latency criteria and focuses on the heuristic search of lightweight implementation for linear layers. Most of the prior approach iteratively combines the inputs (of linear layers) to reach the output, which can be regarded as the forward search. To better adapt the low-latency criteria, we propose a new framework of backward search that attempts to iteratively split every output (into an XORing of two bits) until all inputs appear. By bounding the time of splitting, the new framework can find a sub-optimal solution with a minimized depth of circuits.
We apply our new search algorithm to linear layers of block ciphers and find many low-latency candidates for implementations. Notably, for AES Mixcolumns, we provide an implementation with 103 XOR gates with a depth of 3, which is among the best hardware implementations of the AES linear layer. Besides, we obtain better implementations in XOR gates for 54.3% of 4256 Maximum Distance Separable (MDS) matrices proposed by Li et al. at FSE 2019. We also achieve an involutory MDS matrix (in M4(GL(8, F2))) whose implementation uses the lowest number (i.e., 86, saving 2 from the state-of-the-art result) of XORs with the minimum depth.
|
| first_indexed | 2024-12-13T00:58:10Z |
| format | Article |
| id | doaj.art-8b9f84ce0f8b480395f4084c56fa0416 |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-12-13T00:58:10Z |
| publishDate | 2022-03-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-8b9f84ce0f8b480395f4084c56fa04162022-12-22T00:04:44ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2022-03-012022110.46586/tosc.v2022.i1.158-182Towards Low-Latency Implementation of Linear LayersQun Liu0Weijia Wang1Yanhong Fan2Lixuan Wu3Ling Sun4Meiqin Wang5Key Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, ChinaKey Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, ChinaKey Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, ChinaKey Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, ChinaKey Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, ChinaKey Laboratory of Cryptologic Technology and Information Security, Ministry of Education, Shandong University, Jinan, China; School of Cyber Science and Technology, Shandong University, Qingdao, China; Quan Cheng Shandong Laboratory, Jinan, China Lightweight cryptography features a small footprint and/or low computational complexity. Low-cost implementations of linear layers usually play an important role in lightweight cryptography. Although it has been shown by Boyar et al. that finding the optimal implementation of a linear layer is a Shortest Linear Program (SLP) problem and NP-hard, there exist a variety of heuristic methods to search for near-optimal solutions. This paper considers the low-latency criteria and focuses on the heuristic search of lightweight implementation for linear layers. Most of the prior approach iteratively combines the inputs (of linear layers) to reach the output, which can be regarded as the forward search. To better adapt the low-latency criteria, we propose a new framework of backward search that attempts to iteratively split every output (into an XORing of two bits) until all inputs appear. By bounding the time of splitting, the new framework can find a sub-optimal solution with a minimized depth of circuits. We apply our new search algorithm to linear layers of block ciphers and find many low-latency candidates for implementations. Notably, for AES Mixcolumns, we provide an implementation with 103 XOR gates with a depth of 3, which is among the best hardware implementations of the AES linear layer. Besides, we obtain better implementations in XOR gates for 54.3% of 4256 Maximum Distance Separable (MDS) matrices proposed by Li et al. at FSE 2019. We also achieve an involutory MDS matrix (in M4(GL(8, F2))) whose implementation uses the lowest number (i.e., 86, saving 2 from the state-of-the-art result) of XORs with the minimum depth. https://tosc.iacr.org/index.php/ToSC/article/view/9532Lightweight cryptographyLinear layersLow latencyAES |
| spellingShingle | Qun Liu Weijia Wang Yanhong Fan Lixuan Wu Ling Sun Meiqin Wang Towards Low-Latency Implementation of Linear Layers IACR Transactions on Symmetric Cryptology Lightweight cryptography Linear layers Low latency AES |
| title | Towards Low-Latency Implementation of Linear Layers |
| title_full | Towards Low-Latency Implementation of Linear Layers |
| title_fullStr | Towards Low-Latency Implementation of Linear Layers |
| title_full_unstemmed | Towards Low-Latency Implementation of Linear Layers |
| title_short | Towards Low-Latency Implementation of Linear Layers |
| title_sort | towards low latency implementation of linear layers |
| topic | Lightweight cryptography Linear layers Low latency AES |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/9532 |
| work_keys_str_mv | AT qunliu towardslowlatencyimplementationoflinearlayers AT weijiawang towardslowlatencyimplementationoflinearlayers AT yanhongfan towardslowlatencyimplementationoflinearlayers AT lixuanwu towardslowlatencyimplementationoflinearlayers AT lingsun towardslowlatencyimplementationoflinearlayers AT meiqinwang towardslowlatencyimplementationoflinearlayers |