High-Performance FV Somewhat Homomorphic Encryption on GPUs: An Implementation using CUDA

  • Ahmad Al Badawi Faculty of Engineering, National University of Singapore; A * STAR, Data Storage Institute, Singapore
  • Bharadwaj Veeravalli Faculty of Engineering, National University of Singapore, Singapore
  • Chan Fook Mun A * STAR, Data Storage Institute, Singapore
  • Khin Mi Mi Aung A * STAR, Data Storage Institute, Singapore
Keywords: Homomorphic Encryption, FV, Parallel Processing, GPGPU, CUDA

Abstract

Homomorphic encryption (HE) offers great capabilities that can solve a wide range of privacy-preserving computing problems. This tool allows anyone to process encrypted data producing encrypted results that only the decryption key’s owner can decrypt. Although HE has been realized in several public implementations, its performance is quite demanding. The reason for this is attributed to the huge amount of computation required by secure HE schemes. In this work, we present a CUDAbased implementation of the Fan and Vercauteren (FV) Somewhat HomomorphicEncryption (SHE) scheme. We demonstrate several algebraic tools such as the Chinese Remainder Theorem (CRT), Residual Number System (RNS) and Discrete Galois Transform (DGT) to accelerate and facilitate FV computation on GPUs. We also show how the entire FV computation can be done on GPU without multi-precision arithmetic. We compare our GPU implementation with two mature state-of-the-art implementations: 1) Microsoft SEAL v2.3.0-4 and 2) NFLlib-FV. Our implementation outperforms them and achieves on average 5.37x, 7.37x, 22.22x, 5.11x and 13.18x (resp. 2.03x, 2.94x, 27.86x, 8.53x and 18.69x) for key generation, encryption, decryption, homomorphic addition and homomorphic multiplication against SEAL-FVRNS (resp. NFLlib-FV).

Published
2018-05-08
How to Cite
Badawi, A., Veeravalli, B., Mun, C., & Aung, K. (2018). High-Performance FV Somewhat Homomorphic Encryption on GPUs: An Implementation using CUDA. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2018(2), 70-95. https://doi.org/10.13154/tches.v2018.i2.70-95
Section
Articles