TY - JOUR
T1 - High-speed polynomial multiplication architecture for ring-LWE and SHE cryptosystems
AU - Chen, Donald Donglong
AU - Mentens, Nele
AU - Vercauteren, Frederik
AU - Roy, Sujoy Sinha
AU - Cheung, Ray C.C.
AU - Pao, Derek
AU - Verbauwhede, Ingrid
PY - 2015/1/1
Y1 - 2015/1/1
N2 - 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.
AB - 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.
KW - Cryptography
KW - FFT polynomial multiplication
KW - Field-programmable gate array (FPGA)
KW - Number theoretic transform (NTT)
KW - Pipelined architecture
KW - Polynomial multiplication
KW - Ring-LWE
KW - SHE
UR - http://www.scopus.com/inward/record.url?scp=85027927110&partnerID=8YFLogxK
U2 - 10.1109/TCSI.2014.2350431
DO - 10.1109/TCSI.2014.2350431
M3 - Article
AN - SCOPUS:85027927110
VL - 62
SP - 157
EP - 166
JO - IEEE transactions on circuits and systems. I, Regular papers : a publication of the IEEE Circuits and Systems Society
JF - IEEE transactions on circuits and systems. I, Regular papers : a publication of the IEEE Circuits and Systems Society
SN - 1549-8328
IS - 1
ER -