Reconfigurable Radix-2/4/8 of Unified 2 N Points NTT-INTT for Homomorphic Encryption
Infall Syafalni, Nicholas Teffandi, Fauzan Ibrahim, Indira Pramudita, Nana Sutisna, Trio Adiono · 2025
Fully homomorphic encryption is an encryption that allows direct mathematical operation on its ciphertext. One of the challenges of implementing FHE is the costly operation of polynomial multiplication over an integer ring. One the of candidates to solve this problem is using Number Theoretic Transform (NTT) which is an FFT evaluated on integer ring. In this paper, we propose a unified reconfigurable radix for the NTT-INTT operation to balance between the flexibility of radix-2 to process 2Npoints of polynomial and low computational cycle of higher radix. Experimental results indicate a significant improvement up to 9.06× in throughput per slice when compared to recent alternative designs handling large polynomial inputs (≥ 12), although it remains inferior to architectures optimized for smaller inputs. Nonetheless, this reconfigurable design provides a viable pathway to enhance overall throughput by capitalizing on parallel processing, albeit at the cost of an increased number of slices.