ON THE POLYNOMIAL MULTIPLICATION ALGORITHMS FOR POST-QUANTUM CRYPTOGRAPHY

Lattice-based systems work on polynomial rings. In post-quantum cryptography, polynomial rings of large degree are used to increase security. Among the operations performed on polynomial rings, the most time-consuming operation is multiplication. Therefore, various multiplication algorithms have been proposed to optimize the efficiency of newly developed systems. These algorithms generally aim to reduce the number of multiplications. Thus, the efficiency and cost of the systems are optimized. In this study, Toom-Cook, Karatsuba, NTT, TMVP algorithms are analyzed. Information about the number of reductions in multiplication numbers, their time complexity and the benefits they provide in systems are given. Bruun algorithm, which can be an alternative to the frequently used multiplication algorithms, is described in the method section. Among the polynomial multiplication algorithms, the NTT algorithm is considered to be the most efficient, so we have investigated its potential to increase efficiency. However, it is obvious that within certain criteria, TMVP and Bruun algorithm will provide an effective multiplication reduction in the system.