Paper 2026/2893
Circulant Diffusion Layers: Cost Bounds and Rectangle Reuse
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
-
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}
}