Gate bootstrapping is a core primitive that enables arbitrary circuit evaluation in fully homomorphic encryption (FHE), where blind rotation remains the dominant performance bottleneck. In this work, we present a sub-millisecond NTRU-based gate bootstrapping scheme that achieves state-of-the-art performance through coordinated algorithmic, software, and hardware-level optimizations.

Fully homomorphic encryption (FHE) enables arbitrary computation over encrypted data (ciphertext) without compromising confidentiality. Within this family, TFHE features versatile bootstrapping mechanisms that is attractive for security-critical applications. However, its prohibitive computational cost severely limits practical deployment. While hardware acceleration is promising, mere compute scaling fails to overcome the inherent barriers. In particular, the combination of limited algorithmic parallelism and inadequate understanding of hardware behaviors prevents full exploitation of the available performance headroom.

Fully homomorphic encryption (FHE) enables computations on encrypted data. Existing FHE schemes are primarily categorized into RLWE-based word-wise schemes and LWEbased bit-wise schemes. Efficient combination of different FHE schemes adapted to real-world applications has emerged as a research focus. This paper proposes UniFHE, the first FHE accelerator that supports diverse algebraic structures using general arithmetic units to achieve higher performance. UniFHE is compatible with both RLWE-based and LWE-based FHE schemes without modifications to their original algorithmic designs. To support both finite ring and complex field operations, UniFHE introduces a general arithmetic unit and further constructs core computation structures. To balance on-chip memory demands across different schemes, UniFHE adopts a multi-pipeline architecture for LWE-based schemes. The core functional units for RLWE-based schemes are spliced based on the LWE-based pipelines. Furthermore, an on-chip plaintext encoding mechanism significantly reduces off-chip memory bandwidth demands. Experimental results show that, beyond superior area and energy efficiency, UniFHE delivers up to$13.6 \times$higher performance compared to scheme-specific accelerator combinations. Moreover, in hybrid schemes, UniFHE achieves a$3.2 \times$speedup over the state-of-the-art unified FHE accelerator Trinity.

Abstract Fully Homomorphic Encryption (FHE) enables arbitrary computation on encrypted data without decryption, making it a cornerstone of privacy-preserving outsourcing, such as cloud computing. However, homomorphic operations cause ciphertext noise to grow until decryption fails. The efficient solution is bootstrapping, which refreshes the noise in FHE ciphertexts to sustain arbitrary deep homomorphic evaluation. But in practice, bootstrapping consumes over 50% of total execution time, posing a serious obstacle to FHE adoption. This paper presents a systematic survey of FHE bootstrapping algorithms and their optimizations. We organize existing works into three main paradigms: word-wise bootstrapping for BGV, BFV, and CKKS schemes; bit-wise bootstrapping for FHEW and TFHE schemes; and hybrid bootstrapping, which leverages both word-wise schemes and bit-wise schemes. We analyze the evolution of crucial techniques, highlight latest advances in reducing latency, enhancing parallelism, and controlling noise growth, and compare the advantages and limitations of different schemes. Finally, we discuss emerging research trends.