The number theoretic transform (NTT) is the most widely used technique for accelerating polynomial multiplication in modern cryptographic systems, including homomorphic encryption. In standard NTT computations, the forward NTT (FNTT) and inverse NTT (INTT) operations are realized using Cooley-Tukey (CT) and Gentleman-Sande (GS) butterfly structures. Additionally, the INTT requires an inverse-scaling operation after the transform. These FNTT, INTT, and inverse-scaling operations exhibit different arithmetic structures and dataflow characteristics, resulting in an inherent structural heterogeneity. However, most existing configurable NTT architectures map these heterogeneous operations onto a single shared datapath within a unified butterfly unit. This leads to complex control logic and inefficient hardware resource utilization. In this paper, we optimize arithmetic resource allocation in configurable NTT hardware to address the structural heterogeneity of FNTT, INTT, and inverse‑scaling operations. To realize this approach, we have proposed a configurable NTT hardware architecture that supports multiple polynomial degrees ranging from 2 12 to 2 16 and modulus sizes of up to 64 bits through a structurally aware butterfly datapath. The proposed datapath employs three modular multipliers (one dedicated to each CT butterfly, GS butterfly, and INTT scaling operation) together with lightweight routing multiplexers and arithmetic units. Furthermore, we have presented an area-delay-efficient modular multiplier consisting of a novel integer polynomial multiplier and an optimized Montgomery-based modular reduction architecture. The integer multiplier uses parallel partial-product generation, tree-based accumulation, and shifting techniques, while the Montgomery reduction employs operand digitization and a single instance of the integer multiplier for internal multiplication with the modulus q . Finally, we have proposed benchmarking metrics based on the area-delay product for modular multipliers and the logic-normalized coefficient throughput for the NTT accelerator. The NTT architecture is implemented in Verilog HDL using the Vivado design environment and evaluated up to the post-place-and-route stage on an Artix-7 field-programmable gate array device. Comprehensive performance results and comparisons with state-of-the-art designs confirm that the proposed architecture achieves a significantly lower area with clock cycle overhead, demonstrating its suitability for area-constrained applications.
Sonbul et al. (Mon,) studied this question.