Fast and Energy-Efficient Polynomial Multiplication Using FFT, FFNT, and NTT on GPUs for Fully Homomorphic Encryption

Date

2026-01-01

Author

Özcan, Ali Şah
Tezcan, Cihangir
Savaş, Erkay

Metadata

Show full item record

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.

Item Usage Stats

88
views

0
downloads

Cite This

Many cryptographic schemes, such as fully homomorphic encryption (FHE), zero-knowledge proofs, and post-quantum cryptography, rely on fast multiplication of large polynomials. Efficient algorithms for computing the discrete Fourier transform, including the Fast Fourier Transform (FFT), Negacyclic FFT (FFNT), and Number Theoretic Transform (NTT), can be employed to accelerate these multiplications. In this paper, we introduce an improved version of the FFNT that eliminates pre- and post-processing steps, and we show that it provides competitive performance among FFT- and FFNT-based methods for polynomial multiplication on GPUs, including implementations based on the highly optimized CUDA library cuFFT. We then compare the performance of the proposed FFNT with that of the NTT when both are implemented in CUDA for GPU platforms. Our results show that FFNT can outperform NTT in both speed and energy efficiency on GPUs with sufficiently strong floating-point hardware for some FHE settings. In particular, for polynomial multiplication, the FFNT kernel achieves up to 60% higher energy efficiency than the NTT kernel on such devices. Furthermore, in a practical setting, our GPU-based implementation of torus FHE (TFHE) using FFNT for NAND gate bootstrapping can be up to 46% faster than its NTT-based counterpart when ample floating-point resources are available. These results suggest that the choice between NTT- and FFNT-based polynomial multiplication should be guided by the underlying GPU architecture and by the precision and efficiency requirements of the target FHE workload.

Subject Keywords

Fast Fourier Transform, Fully Homomorphic Encryption, Graphics Processing Units, Negacyclic Fast Fourier Transform, Number Theoretic Transform, Polynomial Multiplication

URI

https://www.scopus.com/inward/record.uri?partnerID=HzOxMe3b&scp=105041272685&origin=inward
https://hdl.handle.net/11511/119635

Collections

Graduate School of Informatics, Conference / Seminar