Utilizing Circulant Structure to Optimize the Implementations of Linear Layers

About

In this paper, we propose a novel approach for optimizing the linear layer used in symmetric cryptography. It is observed that these matrices often have circulant structure. The basic idea of this work is to utilize the property to construct a sequence of transformation matrices, which allows subsequent heuristic algorithms to find more efficient implementations. Our results outperform previous works for various linear layers of block ciphers. For Whirlwind M0 , we obtain two implementations with 159 XOR counts (8% better than Yuan et al. at FSE 2025) and depth 17 (39% better than Shi et al. at AsiaCrypt 2024) respectively. For AES MixColumn, our automated method produces a quantum circuit with depth 10, which nearly matches the manually optimized state-of-the-art result by Zhang et al. at IEEE TC 2024, only with 2 extra CNOTs.

Buji Xu, Xiaoming Sun · 2025

Related benchmarks

Task	Dataset	Result
CNOT circuit synthesis	Matrices used in block ciphers	Circuit Depth3	71
CNOT circuit synthesis	4 x 4 MDS matrices over GL(8, F2)	Circuit Depth8	30
CNOT circuit synthesis	4 x 4 MDS matrices over GL(4, F2)	Circuit Depth8	28
CNOT circuit synthesis	8 x 8 MDS matrices over GL(4, F2)	Circuit Depth20	10
Quantum circuit synthesis for linear layers	AES MixColumns matrix	Circuit Width32	6
XOR gate count optimization	Whirlwind M0	s-XOR Count159	3
XOR gate count optimization	Whirlwind M1	s-XOR Count169	3
XOR gate count optimization	aes	s-XOR105	3
XOR gate count optimization	Clefia M0	s-XOR Count115	3
XOR gate count optimization	Clefia M1	s-XOR Count117	3