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

Research output: Contribution to journalArticlepeer-review


  • Donald Donglong Chen
  • Nele Mentens
  • Frederik Vercauteren
  • Ray C.C. Cheung
  • Derek Pao
  • Ingrid Verbauwhede

Colleges, School and Institutes

External organisations

  • City University of Hong Kong
  • KU Leuven


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