FastNTT: Design and Evaluation of Modular-Reduction Based Fast NTT Design on FPGA

Polynomial multiplication is typically employed to establish secured systems, which is becoming inevitable for many financial and data transaction services. However, the challenge for most cryptosystems is in attaining a computing speed similar to unsecured systems. For a critical transactional activity, the encrypting process lag may allow cyber miscreants to leak information and have irreparable consequences. Hence faster cryptosystems are in demand to serve the purpose of providing security at no computational cost. The Number theoretic transform (NTT) allows compute-latency enhancements by multiplying higher-order polynomials in the transformed domain and achieve the necessary output. The hardware NTT design further tightens the security aspect and additionally offers power-performance benefits to the system. In this paper, Longa-Naehrig reduction technique accompanied with the benefits of Montgomery and Barett reduction was adopted at different stages of NTT sequence generation, to design FPGA based hardware accelerator NTT design referred to as FastNTT, and the same design was further evaluated the same with state-of-the-art (SOTA) NTT implementation on FPGA and in CPU system.The FastNTT scheme for generating 1024 sequence, when designed on FPGA offered performance improvement of 87.30% and 98% with respect to corresponding SOTA implementation on FPGA, and on CPU respectively. Hardware resource savings of 93.75% and 88.57% for flipflops and BRAM respectively was noted by the hardware designed FastNTT technique when compared with its corresponding SOTA designed on FPGA. A power savings of 83.5%, and an improvement in compute-latency of 87.30% is achieved in FastNTT design over SOTA design when implemented on FPGA systems. The hardware design was also synthesized for ASIC flow using 130 nm skywater technology library, which showcased comparable hardware metrics such as critical path delay, and design footprint, however with reduced number of clock cycles for generating NTT sequence, the proposed fast NTT scheme is preferred over other methods. The proposed NTT hardware accelerator is a performance and power-efficient design and is expected to be heavily adopted for polynomial multiplier module design towards designing secured systems in the future.