Quantifying the Overheads of Modular Multiplication

As security and privacy continue to grow in importance, new techniques, including fully homomorphic encryption (FHE) and post-quantum cryptography (PQC), have emerged to provide new capabilities. Many of these techniques are based on the ring learning with errors problem and operate over rings. Elements of a ring are computed using modular arithmetic, with modular multiplication being a primary component. These components are far more complex than standard integer computing, especially when working with large bit widths. As FHE and PQC become increasingly popular, the need for well-designed and optimized modular multipliers also grows in importance. In this paper, we analyze the power, area, performance, energy, and thermal characteristics of two commonly used modular multipliers: Barrett (bit parallel) and Interleaved (bit parallel). To understand these multipliers' characteristics, this study provides necessary insights into the sources of area, power, frequency, and energy overhead, considering a range of different bit widths (16-256). This paper rigorously analyzes the sub-blocks of modular multipliers and their contributions to overall power, performance, and area (PPA).