Efficient number theoretic transform implementation on GPU for homomorphic encryption

Özerk, Özgün and Elgezen, Can and Mert, Ahmet Can and Öztürk, Erdinç and Savaş, Erkay (2022) Efficient number theoretic transform implementation on GPU for homomorphic encryption. Journal of Supercomputing, 78 (2). pp. 2840-2872. ISSN 0920-8542 (Print) 1573-0484 (Online)

This is the latest version of this item.

Full text not available from this repository. (Request a copy)


Lattice-based cryptography forms the mathematical basis for current homomorphic encryption schemes, 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 large 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 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.95× , 105.17× and 90.13× , respectively, on Tesla v100 GPU compared to the highly optimized SEAL library running on an Intel i9-7900X CPU.
Item Type: Article
Uncontrolled Keywords: CUDA; GPU; Homomorphic encryption; Lattice-based cryptography; Number theoretic transform; Polynomial multiplication; SEAL
Divisions: Faculty of Engineering and Natural Sciences
Depositing User: Ahmet Can Mert
Date Deposited: 30 Aug 2022 15:33
Last Modified: 30 Aug 2022 15:33
URI: https://research.sabanciuniv.edu/id/eprint/43686

Available Versions of this Item

Actions (login required)

View Item
View Item