Researchers at the East China Normal University have released a comprehensive study examining the addition complexity of sparse invertible circulant matrices across binary and odd prime fields. Authored by Enyan Li and Gaoli Wang from the Shanghai Key Laboratory of Trustworthy Computing at the Software Engineering Institute, the paper—titled "Circulant Diffusion Layers: Cost Bounds and Rectangle Reuse"—addresses fundamental challenges in the design of efficient cryptographic primitives. The work provides foundational theoretical benchmarks, cost classifications, and explicit circuit constructions aimed at optimizing cryptographic diffusion layers for both low gate counts and shallow circuit depths.
Diffusion is a core principle in modern symmetric cryptography, ensuring that small changes in input data propagate unpredictably across the entire output state. In many block ciphers and hash functions, linear diffusion layers are implemented using Maximum Distance Separable (MDS) matrices or other sparse, invertible matrices to achieve rapid mixing. Circulant matrices—where each row is a cyclic shift of the preceding row—are particularly attractive for hardware and software implementations because their structured algebraic properties significantly reduce memory, wiring, and computational overhead.
However, finding optimal general circuits for these matrices remains a complex computational and mathematical problem, particularly as matrix orders grow larger. To navigate this difficulty, cryptographers often turn to alternative implementation strategies such as rectangle reuse. This approach offers a simpler framework for explicit circuit construction by allowing intermediate values or sub-expressions to be shared and reused across multiple calculations.
In their new paper, Li and Wang undertake a rigorous comparison between general circuit costs, denoted as $Cg$, and rectangle reuse costs, denoted as $Cmathrmrect$. Their findings demonstrate that rectangle reuse can closely approach, and in several significant cases completely attain, the general circuit optimum while simultaneously providing exceptionally shallow implementations under practical cryptographic parameter settings. Circuit depth is a critical metric in high-speed hardware design, as shallower circuits reduce critical path delays and enable higher clock frequencies.
To the best of the authors’ knowledge, this study establishes the first formal lower bounds on both general circuit costs and rectangle reuse costs for general matrices, measured as a function of matrix order and branch numbers. Branch numbers serve as a standard metric for quantifying the diffusion strength of a linear transformation, reflecting the minimum number of active input and output bytes affected by a non-zero difference. By rigorously defining these metrics, the researchers provide a mathematical foundation for evaluating how efficiently a circulant matrix spreads data relative to the computational resources it consumes.
Building upon these initial bounds, the researchers exploit the inherent cyclic structure of circulant matrices to derive precise cost classifications, sharper mathematical boundaries, and explicit constructions optimized for minimum weight. Over the binary field, designated as $mathbbF_2$, the authors provide a complete classification of rectangle costs across all invertible weight-three circulants, determining their exact minimum values for every matrix order $n$ greater than or equal to four. Their analysis reveals that the minimum costs in both the general circuit and rectangle reuse models consistently equal $3n/2$ at every even matrix order, with connected constructions successfully achieving these theoretical minima.
The study extends its findings beyond binary fields to encompass odd prime fields, restricting coefficients to the set containing zero and plus or minus one. Over every odd prime field, connected weight-three constructions similarly attain both the general and rectangle cost minima, specifically achieving $lceil3n/2rceil$ for every matrix order $n$ of four or greater. For matrices exhibiting a branch number of five, the authors prove a rectangle lower bound of $2n$ and successfully construct connected families that attain this bound across infinitely many matrix orders.
Furthermore, for matrices with a branch number of six, Li and Wang leverage the underlying cyclic structure to sharpen general rectangle bounds and determine certified exact rectangle minima at selected matrix orders. These findings offer concrete guidelines for designers working with higher-diffusion layers, where balancing circuit complexity and algebraic security properties becomes increasingly difficult.
The research also addresses the practical implications of connectivity and circuit depth on hardware performance. The authors characterize how structural connectivity influences overall gate efficiency and demonstrate that for weight-three circulants operating over either $mathbbF_2$ or prime fields $mathbbF_p$ where $p$ is greater than or equal to five, the minimum gate count achievable at a circuit depth of two exactly equals the corresponding rectangle cost. This equivalence bridges theoretical circuit complexity and practical hardware engineering, confirming that rectangle reuse strategies do not incur a performance penalty in terms of latency under specific parameter choices.
By combining rigorous lower bounds with explicit, constructive designs, the work provides cryptographers and hardware engineers with robust theoretical benchmarks. These tools are designed to facilitate the creation of next-generation symmetric cryptographic primitives that maintain high security margins while minimizing hardware footprints and execution latency. The complete research paper, cataloged as Paper 2026/2893, is publicly available through the Cryptology ePrint Archive for academic and professional review.

