Low-Complexity NTT and INTT Structures via Twiddle Shifting

Polynomial modular multiplication is an important operation used in post-quantum cryptography and homomorphic encryption, which are based on ring learning with errors (RLWE) problems. For long polynomial lengths, this operation can be efficiently computed using number theoretic transform (NTT) and inverse NTT (INTT). In particular, negative wrapped convolution (NWC) has been proposed to compute this operation where zero padding is eliminated. Low-complexity structures for NTT (LCNTT) and INTT (LC-INTT) have been derived in prior work by using a divide-and-conquer approach. This paper presents an alternate derivation of the LC-NTT and LC-INTT structures from traditional NTT and INTT structures. Specifically, we show that using twiddle factor pushing (pulling) from left to right (right to left), we can derive the prior LC-NTT (LC-INTT) structures. We present systematic algorithms for twiddle factor pushing and pulling to derive the equivalent architectures. The alternate approach may provide opportunities for optimizing hardware implementations of polynomial modular multiplication.