Paper 2020/903

Optimizing Implementations of Linear Layers

Zejun Xiang, Xiangyong Zeng, Da Lin, Zhenzhen Bao, and Shasha Zhang

Abstract

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 de- compositions for a given matrix and optimize those decompositions to pick the best implementation. In order to optimize matrix decompositions, we present several ma- trix 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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A minor revision of an IACR publication in FSE 2020
Contact author(s)
xiangzejun @ hubu edu cn
History
2021-02-25: revised
2020-07-18: received
See all versions
Short URL
https://ia.cr/2020/903
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/903,
      author = {Zejun Xiang and Xiangyong Zeng and Da Lin and Zhenzhen Bao and Shasha Zhang},
      title = {Optimizing Implementations of Linear Layers},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/903},
      year = {2020},
      url = {https://eprint.iacr.org/2020/903}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.