Bootstrapping Optimization for Fully Homomorphic Encryption Schemes

Abstract With the advent of cloud computing and the era of big data, there is an increasing focus on privacy computing. Consequently, homomorphic encryption, being a primary technique for achieving privacy computing, is held in high regard. Nevertheless, the efficiency of homomorphic encryption schemes is significantly impacted by boostrapping. FINAL scheme (ASIACRYPT 2022) is a fully homomorphic encryption scheme based on number theory research unit (NTRU) and learning with errors (LWE) assumptions proposed by Charlotte Bonte et al. The performance of the FINAL scheme is better than TFHE scheme, with a faster bootstrapping and smaller bootstrapping and key-switching keys. In this paper, we introduce ellipsoidal Gaussian sampling to generate the keys f and g in bootstrapping of FINAL scheme, so that the standard deviations of the keys f and g are different and reduce the bootstrapping noise. As a result, larger decomposition bases is used in bootstrapping to reduce the total number of polynomial multiplications, thus improving the efficiency of FINAL scheme. The optimization scheme outperforms the original FINAL scheme with a 33.3\% faster bootstrapping.