Paper Info
Title
RLWE-Oriented High-Speed Polynomial Multiplier Utilizing Multi-Lane Stockham NTT Algorithm
Abstract
Cryptography based on ring learning with error (RLWE) problem has become increasingly popular due to its resistance against quantum analysis. The most time-consuming operation in RLWE cryptosystem is polynomial multiplication. This brief presents a novel polynomial multiplier based on Stockham fast Fourier transform (FFT) algorithm. We propose a multi-lane number theoretic transform (NTT) algorithm which can achieve <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${n}$ </tex-math></inline-formula> -degree polynomial multiplication in <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${(nlgn)/d+2n/d}$ </tex-math></inline-formula> clock cycles with <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${d}$ </tex-math></inline-formula> lanes of butterfly units. In addition, we also customize a memory addressing strategy and a round constant managing scheme for the proposed multi-lane NTT algorithm. Based on our proposed algorithm, a high-speed polynomial multiplier is accomplished on FPGA platform. Implementation results on Spantan-6 FPGA show that our proposed algorithm can achieve a speed up factor of no less than 2.7 times compared with the state of art designs.
Year
DOI
Venue
2020
10.1109/TCSII.2019.2917621
IEEE Transactions on Circuits and Systems II: Express Briefs
Keywords
Field
DocType
Transforms,Clocks,Hardware,Micromechanical devices,Two dimensional displays,Field programmable gate arrays,Indexes
Polynomial,Algorithm,Multiplier (economics),Mathematics
Journal
Volume
Issue
ISSN
67
3
1549-7747
Citations 
PageRank 
References 
3
0.44
0
Authors
3
Name
Order
Citations
PageRank
Xiang Feng1369.16
Shuguo Li24415.97
Sufen Xu330.44