Eniola Olatunji, Adam Montano
Anthony Middleton 

Sponsor or Client: 

Title:

Radix-2 NTT Multiplier For Homomorphic Encryption

Abstract:

The concept revolves around efficient polynomial multiplication, crucial in Homomorphic Encryption (HE) where it is computationally intensive. Standard distributive multiplication has complexity O(N^2), becoming prohibitive as polynomial lengths reach 2^10 to 2^15 in HE ciphertexts. The Number Theoretic Transform (NTT), a Discrete Fourier Transform variant, enables transforming polynomials into the NTT domain for point-wise multiplication, reducing complexity to O(N). Each coefficient multiplies with its counterpart, rather than distributive multiplication, yielding significant performance gains when NTT transformation is efficient.

Initially, a sequential NTT multiplier using the modified DFT NTT equation was implemented. However, its O(N^2) forward transform complexity negated point-wise multiplication benefits. Additionally, storing the large twiddle factor table led to inefficient resource usage and timing issues on hardware. To overcome these limitations, the Cooley-Tukey Fast Fourier Transform Algorithm (CT-FFT) was employed. Introduced in 1965, it exploits symmetry in the twiddle factor table by recursively separating polynomial coefficients into even and odd indices, reducing complexity to O(NlogN).

The implementation utilizes a radix-2 Cooley-Tukey NTT multiplier calculating two coefficients simultaneously using this method. The improved algorithm reduces the twiddle factor table size to N, eliminating dedicated memory needs and simplifying the design. Furthermore, the in-place Cooley-Tukey calculation allows storing polynomials locally within transform modules, optimizing resource utilization. This approach significantly enhances polynomial multiplication efficiency, crucial for Homomorphic Encryption applications.