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 bootstrapping. Enhancing the efficiency of bootstrapping necessitates a dual focus: reducing the computational burden of outer product operations integral to the process while rigorously constraining the noise generated by bootstrapping within predefined threshold limits. The FINAL scheme is a fully homomorphic encryption scheme based on the number theory research unit (NTRU) and learning with errors (LWE) assumptions. The performance of the FINAL scheme is better than that of the TFHE scheme, with faster bootstrapping and smaller bootstrapping and key-switching keys. In this paper, we introduce ellipsoidal Gaussian sampling to generate keys and in the bootstrapping of the FINAL scheme, so that the standard deviations of keys and are different and reduce the bootstrapping noise by 76%. However, when q is fixed, the boundary for bootstrapping noise remains constant. As a result, larger decomposition bases are used in bootstrapping to reduce the total number of polynomial multiplications by 47%, thus improving the efficiency of the FINAL scheme. The optimization scheme outperforms the original FINAL scheme with 33.3% faster bootstrapping, and the memory overhead of blind rotation keys is optimized by 47%.
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.