Efficient VLSI Architecture of Bluestein's FFT for Fully Homomorphic Encryption

Fully homomorphic encryption (FHE) is a powerful scheme that allows computations to be performed on encrypted data. To reduce the computational complexity, double-CRT representation has been adopted in the BGV-FHE cryptosystem, in which the 2nd-CRT, also known as the polynomial-CRT, can be viewed as performing Discrete Fourier Transform (DFT). Since the point size of the DFT is usually non power of two, the traditional Cooley-Tukey FFT algorithm cannot be directly applied to reduce the complexity. This paper explores efficient VLSI architecture of Bluestein's FFT for BGV-FHE applications. A mixed-radix single-port merged-bank memory addressing algorithm is presented to increase the effective memory bandwidth and to reduce the required memory area concurrently. The evaluation was conducted by implementing a Bluestein's FFT compiler that can be configured to generate different point sizes of DFT designs for BGV-FHE. Analytical results also show that the proposed Bluestein's FFT design can lead to a more area-efficient solution as compared to the mixed-radix counterpart in general cases.