KHNTT: A Configurable and High-Performance Polynomial Multiplication Unit Based on FPGA

Polynomial multiplication is a critical performance bottleneck in lattice-based cryptographic schemes, in which efficient and flexible hardware implementations are essential. This paper presents a high-performance and reconfigurable polynomial multiplication unit that integrates the cooptimization of algorithmic and architectural optimizations. As the core operation of polynomial multiplication, we propose the Karatsuba-based high-efficiency radix-4 number theoretic transform (KHNTT) algorithm, which reduces the computational complexity by leveraging low-bit-width arithmetic and parallel processing techniques. Based on this algorithm, we develop a unified radix-4 butterfly unit capable of supporting modular polynomial operations under various parameter configurations, and to further improve the computational efficiency and architectural flexibility, key algorithm modules such as modular reduction and data flow scheduling are deeply optimized. Furthermore, we introduce an iterative interleaving memory strategy combined with a bank resource sharing mechanism to eliminate memory access conflicts and improve data access efficiency. The proposed polynomial multiplication unit allows flexible configuration of the butterfly units and supports polynomial computations of various degrees without the need for recompilation. The FPGA implementation results demonstrate that, compared with existing solutions, our architecture achieves a$1.25\times $to$5.27\times $improvement in the polynomial multiplication throughput and a$1.14\times $to$2.7\times $enhancement in the area efficiency, fully leveraging the computational advantages of FPGAs.