Understanding and boosting fully homomorphic encryption applications on GPU

Abstract Fully Homomorphic Encryption (FHE) is considered one of the most promising candidates for future privacy computing since it allows to directly compute the encrypted data. Though FHE enables secure computation on untrusted servers, its utilization is limited due to the dramatically increased computation workload and a 4–5 orders of magnitude slowdown ratio. Several previous works have been proposed to accelerate FHE on GPUs, while most of these efforts focus on the algorithm or scheduling and still leave a significant performance gap. However, there is a lack of understanding of the FHE applications from the micro-architecture level, which is important for further optimization of FHE applications or designing hardware accelerators. In this paper, we make a detailed analysis for running FHE on GPUs and present the following key performance bottlenecks at the micro-architecture level: (1) FHE applications require more capacity for the I-cache than other workloads; (2) FHE causes large amount of pipeline stalls due to the Read-After-Write (RAW) issues and significantly hurts the performance due to poor hardware utilization; (3) the capacity of texture cache i