FPGA-based Accelerators of Fully Pipelined Modular Multipliers for Homomorphic Encryption

Homomorphic encryption (HE) is an important cryptographic primitive which allows privacy preserving computations. Current HE schemes are all based on modular arithmetic. Modular multiplication (ModMult) is one of the most frequently used modular operations, but in practice it is often prohibitively slow due to a reduction operation with high computational complexity. To address this speed problem, we demonstrate a set of novel FPGA-based accelerators for fully pipelined ModMults in this paper. For a high-throughput integer multiplier (IntMult) in the ModMult designs, digital signal processing (DSP) slices on FPGAs are efficiently exploited with optimized IntMult designs. For the full RNS-HEAAN scheme, which is our target HE scheme, our proposed Barrett ModMult design is optimized using specific moduli and extended to the Shoup ModMult algorithm. Our proposed Barrett and Shoup ModMult designs implemented on a Xilinx Virtex UltraScale FPGA show a 2 × shorter delay, 14× higher throughput at the same frequency, and 3× higher throughput/DSP than the previous non-fully pipelined Barrett ModMult design on average. In particular, our Barrett ModMult design with the specific moduli shows the highest throughput/DSP value although precomputation required in the Shoup ModMult design is not used. Compared with a reference software implementation, our ModMult designs show 679× faster average processing speeds when we deploy multiple ModMult cores that fully use DSP slices on our target FPGA.