Paper 2021/124

Efficient Number Theoretic Transform Implementation on GPU for Homomorphic Encryption

Ozgun Ozerk, Can Elgezen, Ahmet Can Mert, Erdinc Ozturk, and Erkay Savas


Lattice-based cryptography forms the mathematical basis for homomorphic encryption, which allows computation directly on encrypted data. Homomorphic encryption enables privacy-preserving applications such as secure cloud computing; yet, its practical applications suffer from the high computational complexity of homomorphic operations. Fast implementations of the homomorphic encryption schemes heavily depend on efficient polynomial arithmetic; multiplication of very large degree polynomials over polynomial rings, in particular. Number theoretic transform (NTT) accelerates polynomial multiplication significantly and therefore, it is the core arithmetic operation in the majority of homomorphic encryption scheme implementations. Therefore, practical homomorphic applications require efficient and fast implementations of NTT in different computing platforms. In this work, we present an efficient and fast implementation of NTT, inverse NTT (INTT) and NTT-based polynomial multiplication operations for GPU platforms. To demonstrate that our GPU implementation can be utilized as an actual accelerator, we experimented with the key generation, the encryption and the decryption operations of the Brakerski/Fan-Vercauteren (BFV) homomorphic encryption scheme implemented in Microsoft's SEAL homomorphic encryption library on GPU, all of which heavily depend on the NTT-based polynomial multiplication. Our GPU implementations improve the performance of these three BFV operations by up to 141.95x, 105.17x and 90.13x, respectively, on Tesla V100 GPU compared to the highly-optimized SEAL library running on an Intel i9-7900X CPU.

Available format(s)
Publication info
Preprint. MINOR revision.
Lattice-based CryptographyHomomorphic EncryptionSEALNumber Theoretic TransformPolynomial MultiplicationGPUCUDA
Contact author(s)
ozgunozerk @ sabanciuniv edu
celgezen @ sabanciuniv edu
ahmetcanmert @ sabanciuniv edu
erdinco @ sabanciuniv edu
erkays @ sabanciuniv edu
2021-02-05: received
Short URL
Creative Commons Attribution


      author = {Ozgun Ozerk and Can Elgezen and Ahmet Can Mert and Erdinc Ozturk and Erkay Savas},
      title = {Efficient Number Theoretic Transform Implementation on GPU for Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2021/124},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.