SLGP Header

High speed area efficient polynomial multiplication architecture for Ring-LWE and SHE cryptosystems

IJEECC Front Page

In ring-learning with errors (ring-LWE) encryption and "somewhat" homomorphic encryption (SHE) cryptosystemspolynomial multiplication is the basic and most time consuming exhausting operation. In this paper, for the design of the area efficient polynomial multiplier a fast Fourier transform (FFT) is used.. To simplify the control of the architecture a constant geometry FFT datapath is used in the computation. The contribution of this work is three-fold. First, parameter sets that supports both an efficient modular reduction design and the security requirements for ring-LWE encryption and SHE are calculated. 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 and moduli.
Keywords:Cryptography, FFT, Field -Programmable Gate Array(FPGA), Negative wrapped convolution, Number Theoretic Transform, Pipelined Architecture,Polynomial multiplication, Ring-LWE,SHE.


  1. Donald Donglong Chen, FrederikVercauteren,SujoySinha Derek Pao, (january 2015)“High-Speed Polynomial Multiplication Architecture for Ring-LWE and SHE cryptosystems”IEEE transactions on circuits and systems—i: regular papers, vol. 62, no. 1,
  2. OdedRegev, “The Learning with Errors Problem”
  3. VadimLyubashevskyy Chris PeikertzOdedRegevx (June 25, 2013) On Ideal Lattices and Learning with Errors Over Rings.
  4. Daniel J Costello,“Coding for Reliable Digital Transmission and Storage”.
  5. William Stallings, “Cryptography and network security”.
  6. M. Rückert and M. Schneider,( 2010) “Estimating the security of lattice-based cryptosystems,” Cryptology ePrint Archive rep. 2010/137.
  7. K. Lauter, M. Naehrig, and V. Vaikuntanathan, (2011)“Can homomorphicencryptiobe practical?,” in Proc. 3rd ACM Workshop Cloud Comput.Security, , ser. CCSW ’11, pp. 113 124.
  8. Lyubashevsky, D. Micciancio, C. Peikert, and A. Rosen,( 2008) “SWIFFT: A modest proposal for FFT hashing,” in Fast Software Encryption, K. Nyberg, Ed. Berlin/Heidelberg,Germany: Springer, vol. 5086,ser. Lecture Notes in Computer Science, pp. 54–72.
  9. J. M. Pollard,(1971) “The fast Fourier transform in a finite field,” Math. Comput., vol. 25, pp. 365–374.