Bootstrapping Optimization Techniques for the FINAL Fully Homomorphic Encryption Scheme

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 f and g in the bootstrapping of the FINAL scheme, so that the standard deviations of keys f and g 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%.