[Resource Topic] 2023/1815: Accelerating Polynomial Multiplication for RLWE using Pipelined FFT

Welcome to the resource topic for 2023/1815

Accelerating Polynomial Multiplication for RLWE using Pipelined FFT

Authors: Neil Thanawala, Hamid Nejatollahi, Nikil Dutt


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.

ePrint: https://eprint.iacr.org/2023/1815

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .