A survey of optimization techniques for bootstrapping algorithms in FHE

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.