Paper 2021/508

Over 100x Faster Bootstrapping in Fully Homomorphic Encryption through Memory-centric Optimization with GPUs

Wonkyung Jung, Sangpyo Kim, Jung Ho Ahn, Jung Hee Cheon, and Younho Lee


Fully Homomorphic encryption (FHE) has been gaining popularity as an emerging way of enabling an unlimited number of operations on the encrypted message without decryption. A major drawback of FHE is its high computational cost. Especially, a bootstrapping that refreshes the noise accumulated through consequent FHE operations on the ciphertext is even taking minutes. This significantly limits the practical use of FHE in numerous real applications. By exploiting massive parallelism available in FHE, we demonstrate the first GPU implementation for bootstrapping CKKS, one of the most promising FHE schemes that support arithmetic of approximate numbers. Through analyzing FHE operations, we discover that the major performance bottleneck is their high main-memory bandwidth requirement, which is exacerbated by leveraging existing optimizations targeted to reduce computation. These observations lead us to extensively utilize memory-centric optimizations such as kernel fusion and reordering primary functions. Our GPU implementation shows a 7.02x speedup for a single FHE-multiplication compared to the state-of-the-art GPU implementation and 0.423us of amortized bootstrapping time per bit, which corresponds to a speedup of 257x over a single-threaded CPU implementation. By applying this to a logistic regression model training, we achieved a 40.0x speedup compared to the previous 8-thread CPU implementation with the same data.

Available format(s)
Publication info
Preprint. MINOR revision.
GPU accelerationlattice-based cryptographyhomomorphic encryptionCKKS
Contact author(s)
jungwk @ snu ac kr
vnb987 @ snu ac kr
gajh @ snu ac kr
jhcheon @ snu ac kr
younholee @ seoultech ac kr
2021-04-23: received
Short URL
Creative Commons Attribution


      author = {Wonkyung Jung and Sangpyo Kim and Jung Ho Ahn and Jung Hee Cheon and Younho Lee},
      title = {Over 100x Faster Bootstrapping in Fully Homomorphic Encryption through Memory-centric Optimization with GPUs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/508},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.