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

Abstract

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. IEEE Transactions on Circuits and Systems I
DOI
10.1109/TCSI.2014.2350431
Keywords
CryptographyPolynomial multiplicationNumber theoretic transform (NTT)FFT Polynomial multiplicationRing-LWESHEPipelined architectureField-programmable gate array (FPGA)
Contact author(s)
donglongc @ gmail com
History
2014-08-27: received
Short URL
https://ia.cr/2014/646
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/646,
      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{https://eprint.iacr.org/2014/646}},
      url = {https://eprint.iacr.org/2014/646}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.