Memory Usage Reduction over Polynomial Multiplication based on NTT operation

Abstract

In light of the increasing significance of low-end Internet of Things (IoT) devices in our daily lives, the efficiency of algorithm implementation has become a spotlighted topic. Polynomial multiplication over high-dimensional rings, a heavily weighted computation used in many algorithms including certain Post Quantum Cryptography (PQC) algorithms, traditionally necessitates substantial dynamic memory due to the Number Theoretic Transform (NTT) operation. The NTT operation, while effectively lowering the computational complexity from O(n^2) to O(nlog n), poses a significant memory challenge, particularly for resource-constrained IoT devices. This paper presents a novel modification of the traditional NTT and its inverse transform (INTT) operations, aiming to address this memory problem. Our method involves precomputing and storing only the powers of 2 of the primitive root of unity and its inverse, that significantly reduces dynamic memory usage. Simulation results demonstrate the effectiveness of the proposed method, revealing a trade-off between memory usage and computational complexity. While a slight increase in computational complexity is observed, our method yields a considerable reduction in memory requirements, making it valuable for IoT devices. The implications of this research could greatly optimize the implementation of cryptographic algorithms on IoT devices, thereby enhancing their security without overburdening their limited resources.