International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Framework with Improved Heuristics to Optimize Low-Latency Implementations of Linear Layers

Authors:
Haotian Shi , Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China; University of Chinese Academy of Sciences, Beijing, China
Xiutao Feng , Key Laboratory of Mathematics Mechanization, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing, China
Shengyuan Xu , Department of Fundamental Courses, Shandong University of Science and Technology, Taian, 271019, China
Download:
DOI: 10.46586/tosc.v2023.i4.489-510
URL: https://tosc.iacr.org/index.php/ToSC/article/view/11297
Search ePrint
Search Google
Abstract: In recent years, lightweight cryptography has been a hot field in symmetric cryptography. One of the most crucial problems is to find low-latency implementations of linear layers. The current main heuristic search methods include the Boyar-Peralta (BP) algorithm with depth limit and the backward search. In this paper we firstly propose two improved BP algorithms with depth limit mainly by minimizing the Euclidean norm of the new distance vector instead of maximizing it in the tie-breaking process of the BP algorithm. They can significantly increase the potential for finding better results. Furthermore, we give a new framework that combines forward search with backward search to expand the search space of implementations, where the forward search is one of the two improved BP algorithms. In the new framework, we make a minor adjustment of the priority of rules in the backward search process to enable the exploration of a significantly larger search space. As results, we find better results for the most of matrices studied in previous works. For example, we find an implementation of AES MixColumns of depth 3 with 99 XOR gates, which represents a substantial reduction of 3 XOR gates compared to the existing record of 102 XOR gates.
BibTeX
@article{tosc-2023-33697,
  title={A Framework with Improved Heuristics to Optimize Low-Latency Implementations of Linear Layers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={023 No. 4},
  pages={489-510},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/11297},
  doi={10.46586/tosc.v2023.i4.489-510},
  author={Haotian Shi and Xiutao Feng and Shengyuan Xu},
  year=2023
}