The design space of the number theoretic transform: A survey

The Number Theoretic Transform (NTT) is a necessary part of most Lattice-based cryptographic schemes. In particular, it offers an efficient means to achieve polynomial multiplication within the more efficient ring-based schemes. The NTT is also a crucial component which needs to be implemented in a critical way, since it is often the bottle-neck and the most resource consuming block of the whole design. As a result, the NTT is an appealing target for exploring different architectures and design trade-offs. In this paper, we compare various optimization strategies applied to maximize the performance or to reduce the resource utilization. Our analysis covers general purpose processors as well as dedicated hardware implemented on reconfigurable platforms and on ASIC. Previously explored design strategies range from the traditional computation where the multiplicative factors (called twiddle factors) are calculated on-the-fly versus memory trade-off exploration (using memory to store pre-computed twiddle factors), to the use of different butterfly designs for implementing the Fast Fourier Transform and its inverse in software, or the sharing of resources for hardware implementations of the forward and inverse NTT. The problem of side channel resistance is also addressed, discussing designs which are robust against power analysis attacks.