Paper Info
Title
Accelerating number theoretic transform in GPU platform for fully homomorphic encryption
Abstract
In scientific computing and cryptography, there are many applications that involve large integer multiplication, which is a time-consuming operation. To reduce the computational complexity, number theoretic transform is widely used, wherein the multiplication can be performed in the frequency domain with reduced complexity. However, the speed performance of large integer multiplication is still not satisfactory if the operand size is very large (e.g., more than 100K-bit). In view of that, several researchers had proposed to accelerate the implementation of number theoretic transform using massively parallel GPU architecture. In this paper, we proposed several techniques to improve the performance of number theoretic transform implementation, which is faster than the state-of-the-art work by Dai et al. The proposed techniques include register-based twiddle factors storage and multi-stream asynchronous computation, which leverage on the features offered in new GPU architectures. The proposed number theoretic transform implementation was applied to CMNT fully homomorphic encryption scheme proposed by Coron et al. With the proposed implementation technique, homomorphic multiplications in CMNT take 0.27 ms on GTX1070 desktop GPU and 7.49 ms in Jetson TX1 embedded system, respectively. This shows that the proposed implementation is suitable for practical applications in server environment as well as embedded system.
Year
DOI
Venue
2021
10.1007/s11227-020-03156-7
The Journal of Supercomputing
Keywords
DocType
Volume
Number theoretic transform, Homomorphic encryption, Graphics processing unit, Cryptography
Journal
77
Issue
ISSN
Citations 
2
0920-8542
4
PageRank 
References 
Authors
0.44
6
4
Name
Order
Citations
PageRank
Jia-Zheng Goey140.44
Wai-Kong Lee23713.00
Bok-Min Goi349862.02
Wun-She Yap410517.55