Paper 2023/1815

Accelerating Polynomial Multiplication for RLWE using Pipelined FFT

Neil Thanawala, University of California, Irvine
Hamid Nejatollahi, University of California, Irvine
Nikil Dutt, University of California, Irvine

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 the field of 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 present the design of fast and energy-efficient pipelined Number Theoretic Transform (NTT) based polynomial multipliers and present synthesis results on a Field Programmable Gate Array (FPGA) to evaluate their efficacy. 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. The proposed polynomial multiplier with Modr2 architecture reaches 12.5× energy efficiency over the state-ofthe-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.

Available format(s)
Publication info
Contact author(s)
nthanawa @ uci edu
hnejatol @ uci edu
dutt @ ics uci edu
2023-11-27: approved
2023-11-24: received
See all versions
Short URL
No rights reserved


      author = {Neil Thanawala and Hamid Nejatollahi and Nikil Dutt},
      title = {Accelerating Polynomial Multiplication for {RLWE} using Pipelined {FFT}},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1815},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.