Paper 2024/1672 Original: eprint.iacr.org/2024/1672 ↗

New Strategies for Bootstrapping Large-Error Ciphertext in Large-Precision FHEW/TFHE Cryptosystem

Abstract

Bootstrapping is the core task in fully homomorphic encryption. It is designed to self-clean encrypted data to support unlimited level of homomorphic computing. FHEW/TFHE cryptosystem provides the fastest bootstrapping machinery in addition to the unique homomorphic evaluation functionality. In 2021, the problem of large-precision bootstrapping was investigated in the literature, with fast algorithms proposed and implemented. A common strategy to all the algorithms is to decompose the plaintext homomorphically into blocks from the tail up, at the same bootstrap the blocks sequentially. This paper proposes two new strategies to improve the efficiency of large-precision plaintext bootstrapping. Both strategies are based on a new design of continuous nega-cyclic function with varying resolution, for making accurate computation with blockwise approximate computing. To minimize the approximation error in each block, optimizations are proposed based on rigorous error estimation, and are illustrated by error bounds in power-of-two binomial representation. The first strategy is to make homomorphic approximate decomposition of the input plaintext from the head on. Compared with the tail-up approach, the head-on approach reduces the number of blocks at most by half asympotitically, at the same time reducing the final refreshed error by at most $1-1/\sqrt{2}\approx 29.3\%$. The second strategy extends the head-on approach from large-precision plaintext bootstrapping to large error reduction. It can be used directly to the input ciphertext for the purpose of plaintext bootstrapping; it can also be used after plaintext bootstrapping to further reduce the refreshed error. Two algorithms based on the above two strategies are proposed, together with some variants combining the tail-up approach. The tail-up approach is completely re-developed for optimal blocksize control based on careful error analysis, and a corresponding algorithm is proposed. All the algorithms are implemented on PALISADE, and experiments based on real data show that the by the new strategies, the speed of large-precision plaintext bootstrapping can be improved to as many as 7 times.