Accelerating Fully Homomorphic Encryption on

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 Gentry-Halevi (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 computation-intensive 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 large-number number multiplication. In what follows, the Barrett Modular Reduction algorithm is used to realize modular mul-tiplication. We implemented the encryption, decryption and re-cryption 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