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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

71 Scopus Citations
View graph of relations

Author(s)

  • Donald Donglong Chen
  • Nele Mentens
  • Frederik Vercauteren
  • Sujoy Sinha Roy
  • Ingrid Verbauwhede

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number6918547
Pages (from-to)157-166
Journal / PublicationIEEE Transactions on Circuits and Systems I: Regular Papers
Volume62
Issue number1
Online published8 Oct 2014
Publication statusPublished - Jan 2015

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(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.

Research Area(s)

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

Citation Format(s)

High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems. / Chen, Donald Donglong; Mentens, Nele; Vercauteren, Frederik; Roy, Sujoy Sinha; Cheung, Ray C.C.; Pao, Derek; Verbauwhede, Ingrid.

In: IEEE Transactions on Circuits and Systems I: Regular Papers, Vol. 62, No. 1, 6918547, 01.2015, p. 157-166.

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review