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
-
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},
url = {https://eprint.iacr.org/2014/646}
}