Efficient and Compact Full-Domain Functional Bootstrapping via Subring Folding

Functional bootstrapping has emerged as a powerful tool in fully homomorphic encryption (FHE), integrating noise reduction and function evaluation. FHEW/TFHE-based functional bootstrapping has demonstrated high efficiency in evaluating arbitrary non-linear functions, such as typical activation functions in neural networks. Due to the algebraic properties of coefficient embedding over power-of-two cyclotomics, early constructions were limited to evaluating either a negacyclic function under full-domain encoding or an arbitrary function under half-domain encoding. To combine the advantages of arbitrary function evaluation and full-domain encoding, recent works have introduced various techniques to address the challenges posed by negacyclicity. Among these efforts, Xia et al. (TCC 2024) recently showed that this limitation can be entirely circumvented by evaluating the so-called equality test function. However, the substantial noise overhead in their theoretical framework presents a significant challenge toward concretely efficient implementations.In this work, we propose a new full-domain functional bootstrapping algorithm by refining the framework of Xia et al. Our approach introduces a new homomorphic equality test and incorporates several key insights into the Blind Rotation procedure (Chillotti et al., J. Cryptol. 2020), leveraging algebraic properties of power-of-two cyclotomics and their subrings. The resulting algorithm offers the following notable improvements over previous works: (1) one of the most compact bootstrapping key sizes due to significantly reduced noise growth, (2) the most efficient with parallelism enabled by the independence of all involved Blind Rotations, and (3) the ability to evaluate an unbounded number of functions over the same input ciphertext with minimal additional computational cost. Notably, our proof-of-concept implementation under IND-CPAD-secure parameters with multi-threaded CPU execution demonstrates that our new algorithm achieves a 1.4−1.6x speedup compared to the state-of-the-art, alongside a 1.5−2.1x reduction in key size for plaintext precision of 4−6 bits. Our method provides a promising pathway toward parallel-friendly fulldomain functional bootstrapping, with considerable potential for further acceleration on hardware platforms such as GPUs, FPGAs, and ASICs.