High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems

Donald Donglong Chen, Nele Mentens, Frederik Vercauteren, Sujoy Sinha Roy, Ray C.C. Cheung, Derek Pao, Ingrid Verbauwhede

Research output: Contribution to journalArticlepeer-review

62 Citations (Scopus)


Polynomial multiplication is the basic and most computationally intensive operation in ring-learning with errors (ring-LWE) encryption and somewhat homomorphic encryption (SHE) cryptosystems. In this paper, the fast Fourier transform (FFT) with a linearithmic complexity of O(nlog n), is exploited in the design of a high-speed polynomial multiplier. A constant geometry FFT datapath is used in the computation to simplify the control of the architecture. The contribution of this work is three-fold. First, parameter sets which support both an efficient modular reduction design and the security requirements for ring-LWE encryption and SHE are provided. Second, a versatile pipelined architecture accompanied with an improved dataflow are proposed to obtain a high-speed polynomial multiplier. Third, the proposed architecture supports polynomial multiplications for different lengths n and moduli p. The experimental results on a Spartan-6 FPGA show that the proposed design results in a speedup of 3.5 times on average when compared with the state of the art. It performs a polynomial multiplication in the ring-LWE scheme (n=256,p=1049089) and the SHE scheme (n=1024,p=536903681) in only 6.3 μs and 33.1 μs, respectively.

Original languageEnglish
Pages (from-to)157-166
Number of pages10
JournalIEEE Transactions on Circuits and Systems I: Regular Papers
Issue number1
Publication statusPublished - 1 Jan 2015


  • Cryptography
  • FFT polynomial multiplication
  • Field-programmable gate array (FPGA)
  • Number theoretic transform (NTT)
  • Pipelined architecture
  • Polynomial multiplication
  • Ring-LWE
  • SHE

ASJC Scopus subject areas

  • Electrical and Electronic Engineering


Dive into the research topics of 'High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems'. Together they form a unique fingerprint.

Cite this