International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Optimizing Implementations of Linear Layers

Authors:
Zejun Xiang , Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan, China
Xiangyoung Zeng , Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan, China
Da Lin , Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan, China
Zhenzhen Bao , Divison of Mathematical Sciences, School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore, Singapore
Shasha Zhang , Faculty of Mathematics and Statistics, Hubei Key Laboratory of Applied Mathematics, Hubei University, Wuhan, China
Download:
DOI: 10.13154/tosc.v2020.i2.120-145
URL: https://tosc.iacr.org/index.php/ToSC/article/view/8671
Search ePrint
Search Google
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 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.
Video from TOSC 2020
BibTeX
@article{tosc-2020-30540,
  title={Optimizing Implementations of Linear Layers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 2},
  pages={120-145},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/8671},
  doi={10.13154/tosc.v2020.i2.120-145},
  author={Zejun Xiang and Xiangyoung Zeng and Da Lin and Zhenzhen Bao and Shasha Zhang},
  year=2020
}