Integrated NTT-Karatsuba for fast multiplication of NTRU Algorithm - Muhammad Fathan Rivaldi; Rohmat Gunawan; Irani Hoeronis (Faculty of Computer Science (FILKOM) Brawijaya University, 2025)
The increasing threat of attacks from quantum computers requires the development of more efficient and secure post-quantum cryptographic algorithms, one of which is NTRU. The main challenge in this algorithm lies in the high complexity of large-dimensional polynomial multiplication operations and parameter sizes that affect system performance. This research implements the Hybridized Number Theoretic Transform and Karatsuba calculation methods with compressed parameters in the C programming language and integrates them into the NTRU algorithm. The evaluation was conducted by measuring the key generation, encryption, and decryption processing times, as well as analyzing the size of the public key, ciphertext, and bandwidth requirements before and after parameter compression. The experimental results show that this method is able to significantly reduce the modulus q value without compromising security, while increasing execution time efficiency. These findings prove that the hybrid NTT–Karatsuba method with compressed parameters supports the practical implementation of the NTRU algorithm in resource-constrained environments.