Paper 2014/646

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, and Ingrid Verbauwhede


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(n\log 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$\mu$s and 33.1$\mu$s, respectively.

Available format(s)
Publication info
Published elsewhere. MINOR revision.IEEE Transactions on Circuits and Systems I
CryptographyPolynomial multiplicationNumber theoretic transform (NTT)FFT Polynomial multiplicationRing-LWESHEPipelined architectureField-programmable gate array (FPGA)
Contact author(s)
donglongc @ gmail com
2014-08-27: received
Short URL
Creative Commons Attribution


      author = {Donald Donglong Chen and Nele Mentens and Frederik Vercauteren and Sujoy Sinha Roy and Ray C. C.  Cheung and Derek Pao and Ingrid Verbauwhede},
      title = {High-speed Polynomial Multiplication Architecture for Ring-LWE and SHE Cryptosystems},
      howpublished = {Cryptology ePrint Archive, Paper 2014/646},
      year = {2014},
      doi = {10.1109/TCSI.2014.2350431},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.