Full Domain Functional Bootstrapping with Least Significant Bit Encoding

Functional bootstrapping (FBS) is a powerful technique that evaluates a look-up table (LUT) while refreshing an LWE ciphertext in FHEW and TFHE schemes. However, the LUT evaluation over the message space is constrained by negacyclicity, which affects the practical application of functional bootstrapping. Existing methods require multiple FBS and some homomorphic operations to address this issue, which results in inferior performance compared with the original functional bootstrapping. In this paper, we utilize the variant least significant bit (LSB) encoding method to efficiently achieve the full domain functional bootstrapping for message space in FHEW-like schemes. Specifically, the message space \(\mathbb {Z}_t\) is embedded into the encoding space \(\mathbb {Z}_{N}\) by setting the most significant bit of noise to zero. As a result, the encoding space is equal to the domain of the LUT and our functional bootstrapping can evaluate arbitrary functions. In addition, our technique can be applied to multi-value bootstrapping and tree-based bootstrapping. Thus, these algorithms only need one FBS to achieve the full domain property. Finally, we implement our full domain functional bootstrapping in the OpenFHE cryptography library. Experiments demonstrate that up to 2 \(\times \) performance improvement is achieved compared with the state-of-the-art work [27].