Reconfigurable Radix-2/4/8 of Unified 2^N Points NTT-INTT for Homomorphic Encryption

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 2<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">N</sup> points 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.