Barrett Modular Multiplication Optimization for Accelerating Number Theoretic Transform

The practicality of post-quantum lattice-based schemes is crucial for their real-world applications. Integrating these schemes requires efficient implementations through hardware, software, and algorithmic optimisation to achieve the necessary speed and resource capability. This paper aims to improve arithmetic operations in lattice-based cryptography by accelerating the Number Theoretic Transform (NTT/INTT). It optimises the transform’s main bottleneck, the twiddle-factor modular multiplication within the butterfly unit, by replacing it with constant modular multiplication derived from Barrett reduction. We introduce two constant multipliers: the Constant Barrett and a proposed Truncated-Modulus-Size Constant Barrett (TMSCB) variant, which pre-computes each twiddle constant together with its reciprocal, eliminating Barrett’s data dependency and enabling area–time trade-offs. A comprehensive evaluation of the proposed constant modular multiplication is conducted against the classical Barrett multiplication, incorporating analytical complexity analysis and experimental quantitative analysis using FPGA hardware design. The proposed optimisation technique is deployed in the hardware design of the NTT/INTT for the ML-DSA and Falcon parameter sets with optimal use of the DSP cores. Performance comparisons with state-of-the-art implementations of ML-DSA NTT show 46.73% and 29.82% execution time improvements and 17% and 35.4% area resource reductions using single- and dual-butterfly units, respectively. On the Falcon, our design achieves an execution time improvement of at least 27.6%, with area savings across several butterfly configurations. These results validate the effectiveness of the Constant Barrett optimisation technique for accelerating the NTT/INTT, paving the way for more efficient implementations in other applications.