International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

A Framework to Improve the Implementations of Linear Layers

Authors:
Yufei Yuan , Trusted Computing and Information Assurance Laboratory, Institute of Software Chinese Academy of Science, Beijing, 100190, China; University of Chinese Academy of Sciences, Beijing, 100049, China
Wenling Wu , Trusted Computing and Information Assurance Laboratory, Institute of Software Chinese Academy of Science, Beijing, 100190, China; University of Chinese Academy of Sciences, Beijing, 100049, China
Tairong Shi , Trusted Computing and Information Assurance Laboratory, Institute of Software Chinese Academy of Science, Beijing, 100190, China; PLA SSF Information and Engineering University, Zhengzhou, 450001,Henan
Lei Zhang , Trusted Computing and Information Assurance Laboratory, Institute of Software Chinese Academy of Science, Beijing, 100190, China; State Key Laboratory of Cryptology, P.O. Box 5159, Beijing 100878, China
Yu Zhang , Trusted Computing and Information Assurance Laboratory, Institute of Software Chinese Academy of Science, Beijing, 100190, China; University of Chinese Academy of Sciences, Beijing, 100049, China
Download:
DOI: 10.46586/tosc.v2024.i2.322-347
URL: https://tosc.iacr.org/index.php/ToSC/article/view/11633
Search ePrint
Search Google
Abstract: This paper presents a novel approach to optimizing the linear layer of block ciphers using the matrix decomposition framework. It is observed that the reduction properties proposed by Xiang et al. (in FSE 2020) need to be improved. To address these limitations, we propose a new reduction framework with a complete reduction algorithm and swapping algorithm. Our approach formulates matrix decomposition as a new framework with an adaptive objective function and converts the problem to a Graph Isomorphism problem (GI problem). Using the new reduction algorithm, we were able to achieve lower XOR counts and depths of quantum implementations under the s-XOR metric. Our results outperform previous works for many linear layers of block ciphers and hash functions; some of them are better than the current g-XOR implementation. For the AES MixColumn operation, we get two implementations with 91 XOR counts and depth 13 of in-place quantum implementation, respectively.
BibTeX
@article{tosc-2024-34385,
  title={A Framework to Improve the Implementations of Linear Layers},
  journal={IACR Transactions on Symmetric Cryptology},
  publisher={Ruhr-Universität Bochum},
  volume={024 No. 2},
  pages={322-347},
  url={https://tosc.iacr.org/index.php/ToSC/article/view/11633},
  doi={10.46586/tosc.v2024.i2.322-347},
  author={Yufei Yuan and Wenling Wu and Tairong Shi and Lei Zhang and Yu Zhang},
  year=2024
}