Cryptographers and security engineers working on lightweight symmetric ciphers and cryptographic hashing algorithms have long faced a fundamental trade-off: balancing strong cryptographic diffusion with minimal hardware footprint and low latency. A new research paper titled "Circulant Diffusion Layers: Cost Bounds and Rectangle Reuse," authored by Enyan Li and Gaoli Wang from the Shanghai Key Laboratory of Trustworthy Computing at the Software Engineering Institute of East China Normal University, tackles this challenge head-on. The study provides rigorous theoretical cost bounds, precise classifications, and explicit circuit constructions for sparse invertible circulant matrices over binary fields and odd prime fields.
Diffusion layers are critical components in modern block ciphers and cryptographic primitives, responsible for spreading the influence of individual plaintext or state bits across the entire cipher state to achieve the confusion and diffusion properties vital for security. In hardware and software implementations, these layers are frequently built using linear transformations represented by matrices. Circulant matrices—where each row is a cyclic shift of the one above it—are particularly favored by designers because they drastically reduce storage requirements, simplify wiring, and streamline hardware layouts. However, optimizing these layers for minimal addition complexity, gate counts, and circuit depth has remained a notoriously difficult mathematical hurdle, especially as matrix orders scale upward.
To measure diffusion quality, cryptographers rely on branch numbers, a metric that quantifies the minimum number of active input and output components in a linear transformation. Higher branch numbers generally offer stronger resistance against differential and linear cryptanalysis, but they typically demand denser matrices and higher computational overhead. The researchers investigate the addition complexity of sparse invertible circulant matrices over $mathbbF_2$ and odd prime fields, restricting prime field coefficients to the set containing zero and positive or negative one.
Finding optimal general circuits for these matrices is notoriously complex, particularly at large matrix orders where the search space explodes. To circumvent this difficulty, the study explores rectangle reuse as a simpler, more structured alternative for explicit circuit construction. Rectangle reuse allows intermediate values or sub-expressions within a circuit to be shared or reused across multiple operations, potentially reducing the overall number of additions and logic gates required to implement the transformation.
By comparing the general circuit cost, denoted as $Cg$, with the rectangle reuse cost, denoted as $Cmathrmrect$, the authors demonstrate that rectangle reuse can closely approach, and in many instances actually attain, the general circuit optimum. Furthermore, this approach provides shallow implementations that are exceptionally well-suited for practical cryptographic parameter settings, where low latency and high throughput are paramount.
The research breaks new ground by establishing the first known lower bounds on both general circuit costs and rectangle reuse costs for general matrices, linking these costs directly to matrix order and branch numbers. By systematically exploiting the underlying cyclic structure of circulant matrices, Li and Wang are able to derive robust cost classifications, sharpen existing bounds, and deliver explicit, highly optimized constructions operating at minimum weight.
Over the binary field $mathbbF_2$, the authors provide a complete classification of rectangle costs across all invertible weight-three circulants. They successfully determine their exact minimum costs at every matrix order $n$ greater than or equal to four. The findings reveal that the minimum costs in both the general circuit model and the rectangle reuse model equal three times the matrix order divided by two at every even order. Crucially, connected constructions are shown to successfully attain these theoretical minima.
The investigation extends naturally beyond the binary field into odd prime fields. The researchers discover that over every odd prime field, connected weight-three constructions likewise attain both the general and rectangle reuse minima, which equal the ceiling of three times the matrix order divided by two, for every matrix order $n$ greater than or equal to four.
As the study moves to examine higher diffusion requirements, it tackles matrices associated with a branch number of five. For this configuration, the authors prove a rectangle lower bound of twice the matrix order and provide connected families of circuits that successfully attain this bound at infinitely many orders. For branch number six, the research leverages the inherent cyclic structure to sharpen general rectangle bounds and determine certified exact rectangle minima at selected, specific orders.
Finally, the study thoroughly characterizes the combined effects of network connectivity and circuit depth on implementation efficiency. For weight-three circulants operating over $mathbbF_2$ or over prime fields $mathbbF_p$ where $p$ is greater than or equal to five, the minimum gate count achievable at a circuit depth of two is proven to exactly equal the corresponding rectangle cost.
These comprehensive results supply the cryptographic community with essential theoretical cost benchmarks alongside practical, explicit constructions. Together, they offer designers powerful new tools for engineering secure, low-latency circulant diffusion layers characterized by minimal gate counts and shallow circuit depths.






