A GPU library for BFV homomorphic encryption scheme via three different NTT algorithms

Official URL: https://risc01.sabanciuniv.edu/record=b3395405

Homomorphic encryption (HE) is a cryptosystem that allows the secure processing of encrypted data. One of the most popular HE schemes is the Brakerski-Fan-Vercauteren (BFV), which supports somewhat (SWHE) and fully homomorphic encryption (FHE). Since overly involved arithmetic operations of HE schemes are amenable to concurrent computation, GPU devices can be instrumental in facilitating the practical use of HE in real world applications thanks to their superior parallel processing capacity. We propose an optimized and highly parallelized GPU library to accelerate the BFV scheme. The BFV scheme is based on lattice-based cryptography and involves overly many polynomial multiplications of very high degrees and multiprecision coefficients. Since, schoolbook polynomial multiplication is inefficient for GPU at high degrees, firstly, we present three different Number Theoretic Transform (NTT) implementations based on Merge NTT and 4-Step NTT algorithms that are optimized for GPUs instead of using schoolbook multiplicaition. The best of these three implementations employs an approach i) to optimize the number of accesses to slow global memory for thread synchronization, and ii) to make better use of spatial locality in global memory accesses. It turns out that by controlling certain parameters in CUDA platform for general-purpose GPU computing (GPGPU) such as kernel count, block size and block shape, we can affect the performance of NTT. To the best of our knowledge, this work is unique for it suggests a recipe for selecting optimum CUDA parameters to obtain the best NTT performance for a given polynomial degree. Our implementation results on various GPU devices for all powerof- two polynomial degrees from 212 to 228 show that our algorithms compare favorably with the other state-of-the-art GPU implementations in the literature with the optimum selection of these three CUDA parameters. Furthermore, NTT can also be used in Zero- Knowledge systems apart from Homomorphic Encryption because it can work with high ring sizes. The library also improves the performance of the homomorphic operations of the BFV scheme. Although the library can be independently used, it is also fully integrated with the Microsoft SEAL library, which is a well-known HE library that also implements the BFV scheme. For one ciphertext multiplication, for the ring dimension 214 and the modulus bit size of 438, our GPU implementation offers 361.6 times speedup over the SEAL library running on a high-end CPU. The library compares favorably with other state-of-the-art GPU implementations of NTT and BFV operations. Finally, we implement a privacy-preserving application that classifies encrypted genome data for tumor types and achieves speedups of 237.88 and 36.08 over CPU implementations using single and 16 threads, respectively. Our results indicate that GPU implementations can facilitate the deployment of homomorphic cryptographic libraries in real-world privacy-preserving applications.