Accelerating Homomorphic Full Adder based on FHEW Using Multicore CPU and GPUs

The latest implementation of the fully homomorphic encryption algorithm (FHEW), FHEW-V2, takes about 0.12 s for a bootstrapping on a single-node computer. It seems much faster than the previous implementations. However, the 30-bit homomorphic addition requires 270 times of bootstrapping; plus those spent on key generation, the total elapsed time climbs to 55 seconds, which is unacceptable. In this article, we reveal how to further optimize FHEW-V2 by focusing on efficiently constructing homomorphic full adders. We tackle inefficiency in FHEW-V2 by massive efforts: First, we explore FHEW-V2 and locate hotspots; second, we leverage the heterogeneous parallel computing model of multicore CPU and GPUs to remove the hotspots to improve performance. The empirical results show that a 30-bit homomorphic addition is completed in 23.8753 s after optimization, gaining an overall speedup of 2.2845; and a 6-bit homomorphic multiplication costs 25.8438, gaining an overall speedup of 2.2435. The 2.2845 speedup is a rough integration of a 13.248 speedup for the key generation and a 1.672 speedup for the bootstrapping; the 2.2435 speedup is a rough integration of the same key generation and a 1.675 speedup for the bootstrapping. We also reveal the strengths and weaknesses of FHEW-V2 by comparing it with a state-of-the-art somewhat homomorphic encryption algorithm, microsoft’s simple encrypted arithmetic library (SEAL).