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 seconds for a bootstrapping on a single-node computer. It seems much faster than the previous implementations. However, a 30-bit homomorphic full adder requires 270 times of bootstrapping, plus the time spent on key generation, the total elapsed time will be 55 seconds, which is unacceptable. In this paper, we reveal how to improve further the performance of FHEW-V2 by specifically focusing on the optimization of a homomorphic full adder. We strive to tackle the inefficiency in FHEW-V2 by massive efforts: first, we explore the reference codes for FHEW-V2 and find out hotspot codes for performance optimization; second, we leverage the computing power of multicore CPU and GPUs to remove the hotspots to improve performance. The empirical results so far show that a 30-bit homomorphic full adder is completed in 24 seconds after optimization, gaining an overall speedup of 2.2845. The 2.2845 speedup is the integration of a 13.248 speedup for the key generation and a 1.672 speedup for the bootstrapping.