Performance and Overflow Analysis of Polynomial Multiplication with Lazy Reduction in LightSaber

Polynomial multiplication is the main operation in lattice-based cryptography. Modular reduction is required to maintain the correctness within finite rings. In this study, the application of lazy reduction is chosen to reduce the frequency of modular operations in the LightSaber cryptosystem. Four polynomial multiplication algorithms, including Schoolbook, Karatsuba (128 and 64 splits), and Toom-3, are evaluated under both conventional and lazy reduction settings within the same polynomial ring domain. The experimental results show that lazy reduction reduces execution time across all evaluated algorithms. The reductions range from 44.52% to 59.15%. When the number of modular reduction operations is considered, they are reduced by more than 99% for Schoolbook and Karatsuba-based methods, and by 57.14% for Toom-3. Under lazy reduction, the number of modular reductions becomes identical across all algorithms. Among the evaluated coefficient-domain methods, Toom-3 achieved the lowest execution time. Karatsuba-based methods provide a more balanced trade-off between performance, memory usage, and structural complexity. This study further examines coefficient growth and evaluates the risk of overflow to ensure numerical reliability. All intermediate values remain within the range of signed 32-bit integers. Furthermore, lazy reduction leads to an increase in peak memory usage across all algorithms, with the most significant increase observed in Schoolbook, while more advanced methods exhibit only modest growth. Since this study focuses on coefficient-domain polynomial multiplication, transform-based approaches such as the Number Theoretic Transform (NTT) are beyond the scope of this work. NTT operates in a different computational domain and involves distinct implementation trade-offs. Accordingly, the reported performance comparisons are restricted to the coefficient-domain methods evaluated in this study. In addition, hardware-specific evaluations are beyond the scope of this work, because the primary objective is to provide an algorithm-level analysis of computational efficiency, modular reduction behavior, and numerical safety under controlled conditions. Under the evaluated Python implementation and the LightSaber parameter configuration, the results show that lazy reduction is an effective technique for reducing computational overhead in coefficient-domain polynomial multiplication. The observed performance remains dependent on the structural characteristics of each multiplication algorithm.