Accelerating Fully Homomorphic Encryption on GPUs
Department of Electrial and Computer Engineering, Worcester Polytechnic Institute, Worcester, MA, USA
IEEE High Performance Extreme Computing Conference(HPEC ’12), 2012
@article{wang2012accelerating,
title={Accelerating Fully Homomorphic Encryption on GPUs},
author={Wang, W. and Hu, Y. and Chen, L. and Huang, X. and Sunar, B.},
year={2012}
}
In a major breakthrough, in 2009 Gentry introduced the first plausible construction of a fully homomorphic encryption (FHE) scheme. FHE allows the evaluation of arbitrary functions directly on encrypted data on untwisted servers. In 2010, Gentry and Halevi presented the first FHE implementation on an IBM x3500 server. However, this implementation remains impractical due to the high latency of encryption and recryption. The GentryHalevi (GH) FHE primitives, utilize multi-million-bit modular multiplications and additions – time-consuming tasks for general purpose processors. In the GH-FHE implementation, the most computationintensive arithmetic operation is modular multiplication. In this paper, the million-bit multiplication is calculated in two steps: large-number multiplication and modular reduction. Strassen’s FFT based algorithm is used so that Graphics processing units (GPU) can employ massive parallelism to accelerate the largenumber number multiplication. In what follows, the Barrett Modular Reduction algorithm is used to realize modular multiplication. We implemented the encryption, decryption and recryption primitives on the NVIDIA C2050. Experimental results show factors of up to 7.68, 7.4 and 6.59 speed improvement for encryption, decryption and recrypt, respectively, when compared to the GH implementation for the small setting in dimension 2048.
October 16, 2012 by hgpu
