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

Available format(s)
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
Short URL
https://ia.cr/2014/646

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.