Number Theoretic Transform: Generalization, Optimization, Concrete Analysis and Applications

Number theoretic transform (NTT) is a basic mathematic operation, and is particularly fundamental to the practical implementations of cryptographic algorithms based on lattices with algebraic structures. In this work, we make a systematic and comprehensive study of NTT and its variants. We first review the NTT technique and the recent advances raised in the implementations of practical lattice-based cryptography. We clarify the relationship of some existing NTT variants, and prove their computational equivalence. We then make the generalizations of NTT, analyze their exact computational complexity, and derive the optimal bounds. Finally, we show the applications of our results to some prominent practical lattice-based algorithms.