Parallel Accelerating Number Theoretic Transform for Bootstrapping on a Graphics Processing Unit

Huixian Li (), Deng Pan, Jinglei Li and Hao Wang
Additional contact information
Huixian Li: School of Computer Science, Northwestern Polytechnical University, Xi’an 710072, China
Deng Pan: School of Computer Science, Northwestern Polytechnical University, Xi’an 710072, China
Jinglei Li: College of Data Science and Application, Inner Mongolia University of Technology, Huhhot 010080, China
Hao Wang: School of Software, Northwestern Polytechnical University, Xi’an 710072, China

Mathematics, 2024, vol. 12, issue 3, 1-15

Abstract: The bootstrapping procedure has become the main bottleneck affecting the efficiency of all known fully homomorphic encryption (FHE) schemes. The state-of-the-art scheme for efficient bootstrapping, which is called fully homomorphic encryption over the torus (TFHE), accelerates polynomial multiplication by leveraging number theoretic transform (NTT) and implementing NTT in parallel on a GPU. Unfortunately, almost none of the recent advancements in NTT take full advantage of a GPU, leading to the need for more time. With this in mind, in this work, a novel faster number theoretic transform based on a GPU is proposed, in which matrix multiplication is used to implement a decomposed small-point NTT. When implementing matrix multiplication, we introduce a merging preprocessing method to merge multiple inputs of the small-point NTT, aiming to effectively minimize the count of modulo operations. Subsequently, when the merged result is multiplied by rotation factors, we use logical left shift rather than arithmetic multiplication to improve the computational efficiency. Our scheme can easily be used to realize a 1024-point NTT and the results of the experiments show that the speedup ratio of our method over the butterfly algorithm is about 2.49.

Keywords: fully homomorphic encryption; TFHE; bootstrapping; GPU; NTT; polynomial multiplication (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2024
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/12/3/458/pdf (application/pdf)
https://www.mdpi.com/2227-7390/12/3/458/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:12:y:2024:i:3:p:458-:d:1330444

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().