FAST: FPGA Acceleration of Fully Homomorphic Encryption with Efficient Bootstrapping

Bootstrapping is a critical operation in Fully Homomorphic Encryption (FHE) for privacy-preserving computation. Due to its significant computational overhead, accelerating bootstrapping is crucial for practical FHE applications involving deep evaluation circuits. In this paper, we introduce FAST, an FPGA-based accelerator for efficient FHE bootstrapping. We propose novel datapath optimizations for two key operations in bootstrapping: homomorphic linear transformation (HLT) and polynomial evaluation. Our memory-efficient datapath designed for HLT significantly reduces off-chip ciphertext access. We also speed up the polynomial evaluation process by reducing the number of required HE operations. We conduct an in-depth analysis of the Advanced Bootstrapping Algorithm (ABA) and highlight its computational advantages. FAST is the first accelerator to support ABA, demonstrating significant speedup for bootstrapping. In addition, we develop a novel versatile permutation circuit to handle diverse permutation patterns in FHE, achieving high throughput and efficient resource utilization. Compared with the state-of-the-art (SOTA) GPU and FPGA designs, FAST achieves 8.84× and 5.89× speedups for bootstrapping, respectively. As illustrative examples of deep FHE applications, we show that FAST delivers over 20× speedup for logistic regression training compared with the SOTA GPU implementation and outperforms the SOTA FPGA design by 1.43× for ResNet-20 inference.