Hardware Acceleration of Polynomial Multiplication using Pipelined FFT
- Author(s): Thanawala, Neil
- Advisor(s): Dutt, Nikil
- et al.
The evolution of quantum algorithms threatens to break public key cryptography in polynomial time. The development of quantum-resistant algorithms for the post-quantum era has seen a significant growth in a field called post quantum cryptography (PQC). Polynomial multiplication is the core of Ring Learning with Error (RLWE) lattice based cryptography (LBC) which is one of the most promising PQC candidates. In this work, we design Number Theoretic Transform (NTT) based polynomial multipliers and synthesize on a Field Programmable Gate Array (FPGA). NTT is performed using the pipelined R2SDF and R22SDF Fast Fourier Transform (FFT) architectures. In addition, we propose an energy efficient modified architecture (Modr2). The NTT-based designed polynomial multipliers employs the Modr2 architecture that achieve on average 2× better performance over the R2SDF FFT and 2.4× over the R22SDF FFT with similar levels of energy consumption. Polynomial multiplication using the Modr2 architecture developed in this thesis shows 12.5× energy efficiency over the state-of-the-art convolution-based polynomial multiplier and 4× speedup over the systolic array NTT based polynomial multiplier for polynomial degrees of 1024, demonstrating its potential for practical deployment in future designs.