A Comparative Analysis between Karatsuba, Toom-Cook and NTT Multiplier for Polynomial Multiplication in NTRU on FPGA

Post-quantum cryptography (PQC) is a rapidly growing field that aims to develop cryptographic algorithms that can resist attacks by quantum computers. Large-degree polynomial multiplication is an essential mathematical operation for lattice-based post-quantum cryptographic algorithms like CRYSTALS-Kyber, Dilithium, and NTRU. Due to the complexity involved in modular arithmetic, large-degree polynomial multiplication is a critical operation that needs to be accelerated for fast execution of the underlying cryptographic algorithms. In this paper, we aim to provide a comparative case study that focuses on analyzing the effectiveness of Karatsuba, Toom-Cook, and Number theoretic transform (NTT) based multipliers for performing polynomial multiplication in NTRU that uses NTT unfriendly quotient q. Our proposed Karatsuba-based implementation is based on the overlap-free version, and for Toom-Cook, we have used a three-way decomposition. Our result shows that for NTRU, the proposed overlap-free Karatsuba architecture provides a better area delay product than the Toom-cook architecture, even though the Toom-cook algorithm is asymptotically faster than the Karatsuba. Additionally, we have implemented NTRU polynomial multiplication using NTT by performing NTT prime lifting, which exhibits a low area and a compact architecture. This comparative study between different multiplier architectures would enable the hardware designer to choose the suitable multiplier depending on their requirement.