A Note on the Implementation of the Number Theoretic Transform

摘要

The Number Theoretic Transform (NTT) is a time critical function required by many post-quantum cryptographic protocols based on lattices. For example it is commonly used in the context of the Ring Learning With Errors problem (RLWE), which is a popular basis for post-quantum key exchange, digital signature, and encryption. Here we apply a simple methodology to convert the NTT and its inverse from a mathematically correct (but side-channel vulnerable) description, to an efficient constant-time and side-channel resistant version.