Accelerating an FHE Integer Multiplier Using Negative Wrapped Convolution and Ping-Pong FFT

This brief proposes a novel hardware structure for large integer multiplication in fully homomorphic encryption. We propose a method based on negative wrapped convolution to avoid zero padding in Strassen's algorithm, which can cut down half of the Fourier transform length. In addition, we also optimize the ping-pong fast Fourier transform algorithm by doubling the transform throughput and generating the round constant on the fly. Based on our proposed method and optimized algorithm, we design and implement a 768 k-bit integer multiplier on Altera Stratix V field-programmable gate array (FPGA). Implementation results on FPGA show that our structure outperforms the current competitors in area efficiency.