A configurable and efficient implementation of Number Theoretic Transform (NTT) for lattice based Post-Quantum-Cryptography

Advancement in the quantum computer has imposed huge threat to modern cryptography techniques. Post quantum cryptography (PQC) based on lattice structure provides quantum-resistance and facilitates efficient hardware implementation compared to other solutions. Ring learning with errors (RLWE) is a basic primitive of lattice-based cryptosystem, defined on a polynomial quotient ring with time and resource consuming multiplication operations. Number Theoretic Transform (NTT) is an extensively used polynomial multiplier to achieve AreaX-Time trade-off. In this paper, we proposed a fully configurable NTT which supports different RLWE and design parameters to produce highly optimized hardware. Our design can be customized for higher throughput or lightweight applications. The proposed high performance design achieves 9X improvement in execution time compared to High-Level synthesis, pure software and various hardware implementations. The result shows that our lightweight architecture consumes 16X lesser resource than other FPGA solutions targeted for deeply embedded systems. The proposed design is experimented in the NewHope PQC key exchange application and the execution time is enhanced by 37% at 133 MHz clock frequency compared to recent implementations.