New Integer-FFT Multiplication Architectures and Implementations for Accelerating Fully Homomorphic Encryption
This paper proposes a new hardware architecture of Integer-FFT multiplier for super-size integer multiplications. Firstly, a basic hardware architecture, with the feature of low hardware cost, of the Integer-FFT multiplication algorithm using the serial FFT architecture, is proposed. Next, a modified hardware architecture with a shorter multiplication latency than the basic architecture is presented. Thirdly, both architectures are implemented, verified and compared on the Xilinx Virtex-7 FPGA platform using 256, 512, 1024, 2048 and 8192 point Integer-FFT algorithm respectively with multiplication operands ranging from bits to bits in size. Experimental results show that the hardware cost of the proposed architecture is no more than 1/10 of the prior FPGA solution, and is perfectly within the implementable range of the Xilinx Virtex-7 FPGA platform, and outperforms the software implementations of the same bit-length operand multiplication on the Core-2 Q6600 and Core-i7 870 platforms. Finally, the proposed implementations are employed to evaluate the super-size multiplication in an encryption primitive of fully homomorphic encryption (FHE) over the integers. The analysis shows that the speed improvement factor is up to 26.2 compared to the corresponding integer-based FHE software implementation on the Core-2 Duo E8400 platform.