Paper 2026/2893

Circulant Diffusion Layers: Cost Bounds and Rectangle Reuse

Enyan Li, Shanghai Key Laboratory of Trustworthy Computing, Software Engineering Institute, East China Normal University, Shanghai 200062, China
Gaoli Wang, Shanghai Key Laboratory of Trustworthy Computing, Software Engineering Institute, East China Normal University, Shanghai 200062, China
Abstract

We study the addition complexity of sparse invertible circulant matrices over $\mathbb{F}_2$ and odd prime fields. Diffusion is measured by branch numbers, and prime field coefficients are restricted to $\{0,\pm1\}$. Finding optimal general circuits is often difficult, particularly at large matrix orders. Rectangle reuse offers a simpler alternative for explicit circuit construction. We compare the general circuit cost $C_g$ with the rectangle reuse cost $C_{\mathrm{rect}}$, and show that rectangle reuse can approach, and sometimes attain, the general circuit optimum while providing shallow implementations in practical cryptographic parameter settings. To the best of our knowledge, we establish the first lower bounds on both $C_g$ and $C_{\mathrm{rect}}$ for general matrices in terms of matrix order and branch numbers. We then exploit cyclic structure to obtain cost classifications, sharper bounds, and explicit constructions at minimum weight. Over $\mathbb{F}_2$, we give a complete classification of rectangle costs over all invertible weight-three circulants and determine their exact minima at every order $n\ge4$. The minimum costs in both the general circuit and rectangle reuse models equal $3n/2$ at every even order, with connected constructions attaining these minima. Over every odd prime field, connected weight-three constructions likewise attain both minima, namely $\lceil3n/2\rceil$, for every $n\ge4$. For branch number five, we prove the rectangle lower bound $2n$ and give connected families attaining it at infinitely many orders. For branch number six, we exploit cyclic structure to sharpen the general rectangle bounds and determine certified exact rectangle minima at selected orders. Finally, we characterize the effects of connectivity and circuit depth. For weight-three circulants over $\mathbb{F}_2$ or $\mathbb{F}_p$ with $p\ge5$, the minimum gate count at depth two equals the rectangle cost. These results provide theoretical cost benchmarks and explicit constructions for designing circulant diffusion layers with low gate counts and shallow circuits.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Preprint.
Keywords
Lightweight cryptographydiffusion layerscirculant matricesbranch numberaddition complexity
Contact author(s)
lienyan6 @ gmail com
glwang @ sei ecnu edu cn
History
2026-11-18: approved
2026-11-14: received
See all versions
Short URL
https://ia.cr/2026/2893
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2893,
      author = {Enyan Li and Gaoli Wang},
      title = {Circulant Diffusion Layers: Cost Bounds and Rectangle Reuse},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2893},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2893}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.