{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T00:58:26Z","timestamp":1760057906410,"version":"build-2065373602"},"reference-count":29,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T00:00:00Z","timestamp":1741132800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"Fund of the Laboratory for Advanced Computing and Intelligence Engineering","award":["2023-LYJJ-01-002"],"award-info":[{"award-number":["2023-LYJJ-01-002"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>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%.<\/jats:p>","DOI":"10.3390\/info16030200","type":"journal-article","created":{"date-parts":[[2025,3,5]],"date-time":"2025-03-05T03:18:22Z","timestamp":1741144702000},"page":"200","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Bootstrapping Optimization Techniques for the FINAL Fully Homomorphic Encryption Scheme"],"prefix":"10.3390","volume":"16","author":[{"given":"Meng","family":"Wu","sequence":"first","affiliation":[{"name":"College of Cryptography Engineering, Information Engineering University, Zhengzhou 450001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9737-6842","authenticated-orcid":false,"given":"Xiufeng","family":"Zhao","sequence":"additional","affiliation":[{"name":"College of Cryptography Engineering, Information Engineering University, Zhengzhou 450001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6474-2298","authenticated-orcid":false,"given":"Weitao","family":"Song","sequence":"additional","affiliation":[{"name":"College of Cryptography Engineering, Information Engineering University, Zhengzhou 450001, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"831","DOI":"10.1137\/120868669","article-title":"Efficient fully homomorphic encryption from (standard) LWE","volume":"43","author":"Brakerski","year":"2014","journal-title":"SIAM J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/2633600","article-title":"(Leveled) fully homomorphic encryption without bootstrapping","volume":"6","author":"Brakerski","year":"2014","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Brakerski, Z. (2012). Fully homomorphic encryption without modulus switching from classical GapSVP. Annual Cryptology Conference, Springer.","DOI":"10.1007\/978-3-642-32009-5_50"},{"key":"ref_4","unstructured":"Fan, J., and Vercauteren, F. (2025, January 13). Somewhat Practical Fully Homomorphic Encryption. Cryptology ePrint Archive. Available online: https:\/\/eprint.iacr.org\/2012\/144."},{"key":"ref_5","unstructured":"Cheon, J.H., Kim, A., Kim, M., and Song, Y. (2017, January 3\u20137). Homomorphic encryption for arithmetic of approximate numbers. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China. Proceedings, Part I 23."},{"key":"ref_6","doi-asserted-by":"crossref","unstructured":"Ducas, L., and Micciancio, D. (2015, January 26\u201330). FHEW: Bootstrapping homomorphic encryption in less than a second. Proceedings of the 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria.","DOI":"10.1007\/978-3-662-46800-5_24"},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., Georgieva, M., and Izabachene, M. (2016, January 4\u20138). Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2016: 22nd International Conference on the Theory and Application of Cryptology and Information Security, Hanoi, Vietnam. Proceedings, Part I 22.","DOI":"10.1007\/978-3-662-53887-6_1"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., Georgieva, M., and Izabach\u00e8ne, M. (2017, January 3\u20137). Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. Proceedings of the 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China.","DOI":"10.1007\/978-3-319-70694-8_14"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Bonte, C., Iliashenko, I., Park, J., Pereira, H.V., and Smart, N.P. (2022, January 5\u20139). Final: Faster fhe instantiated with ntru and lwe. Proceedings of the 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan.","DOI":"10.1007\/978-3-031-22966-4_7"},{"key":"ref_10","doi-asserted-by":"crossref","unstructured":"Gentry, C., Sahai, A., and Waters, B. (2013, January 18\u201322). Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Proceedings of the Advances in Cryptology\u2013CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA. Proceedings, Part I.","DOI":"10.1007\/978-3-642-40041-4_5"},{"key":"ref_11","unstructured":"Alperin-Sheriff, J., and Peikert, C. (2014, January 17\u201321). Faster bootstrapping with polynomial error. Proceedings of the Advances in Cryptology\u2013CRYPTO 2014: 34th Annual Cryptology Conference, Santa Barbara, CA, USA. Proceedings, Part I 34."},{"key":"ref_12","unstructured":"Gentry, C. (2009). A Fully Homomorphic Encryption Scheme, Stanford University."},{"key":"ref_13","first-page":"1","article-title":"Gaussian sampling in lattice based cryptography","volume":"60","year":"2014","journal-title":"Tatra Mt. Math. Publ."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Genise, N., Micciancio, D., and Polyakov, Y. (2019, January 19\u201323). Building an efficient lattice gadget toolkit: Subgaussian sampling and more. Proceedings of the Advances in Cryptology\u2013EUROCRYPT 2019: 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Darmstadt, Germany. Proceedings, Part II 38.","DOI":"10.1007\/978-3-030-17656-3_23"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"17429","DOI":"10.1109\/ACCESS.2021.3053288","article-title":"Efficient lattice gadget decomposition algorithm with bounded uniform distribution","volume":"9","author":"Jeon","year":"2021","journal-title":"IEEE Access"},{"key":"ref_16","unstructured":"Stehl\u00e9, D., and Steinfeld, R. (2011, January 15\u201319). Making NTRU as secure as worst-case problems over ideal lattices. Proceedings of the Advances in Cryptology\u2013EUROCRYPT 2011: 30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia. Proceedings 30."},{"key":"ref_17","unstructured":"Pellet-Mary, A., and Stehl\u00e9, D. (2021, January 6\u201310). On the hardness of the NTRU problem. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore. Proceedings, Part I 27."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1561\/0400000074","article-title":"A decade of lattice cryptography","volume":"10","author":"Peikert","year":"2016","journal-title":"Found. Trends\u00ae Theor. Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Ligier, D., Orfila, J.B., and Tap, S. (2021, January 6\u201310). Improved Programmable Bootstrapping with Larger Precision and Efficient Arithmetic Circuits for TFHE. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore. Proceedings, Part III 27.","DOI":"10.1007\/978-3-030-92078-4_23"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1587\/transfun.E99.A.73","article-title":"Packing messages and optimizing bootstrapping in GSW-FHE","volume":"99","author":"Hiromasa","year":"2016","journal-title":"IEICE TRANSACTIONS Fundam. Electron. Commun. Comput. Sci."},{"key":"ref_21","first-page":"2117","article-title":"Research on circular secure homomorphic encryption scheme","volume":"57","author":"Xiufeng","year":"2020","journal-title":"J. Comput. Res. Dev."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Espitau, T., Tibouchi, M., Wallet, A., and Yu, Y. (2022). Shorter hash-and-sign lattice-based signatures. Annual International Cryptology Conference, Springer.","DOI":"10.1007\/978-3-031-15979-4_9"},{"key":"ref_23","first-page":"708","article-title":"Two birds with one stone: Two-factor authentication with security beyond conventional bound","volume":"15","author":"Wang","year":"2016","journal-title":"IEEE Trans. Dependable Secur. Comput."},{"key":"ref_24","first-page":"845","article-title":"Leakage Resilient Leveled FHE on Multiple Bits Message","volume":"7","author":"Li","year":"2017","journal-title":"IEEE Trans. Big Data"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Yu, Y., Xu, G., and Wang, X. (2017, January 28\u201331). Provably secure NTRU instances over prime cyclotomic rings. Proceedings of the 20th IACR International Conference on Practice and Theory in Public-Key Cryptography, Amsterdam, The Netherlands.","DOI":"10.1007\/978-3-662-54365-8_17"},{"key":"ref_26","first-page":"1","article-title":"Falcon: Fast-Fourier lattice-based compact signatures over NTRU","volume":"36","author":"Fouque","year":"2018","journal-title":"Submiss. NIST S Post-Quantum Cryptogr. Stand. Process"},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"Ducas, L., Lyubashevsky, V., and Prest, T. (2014, January 7\u201311). Efficient identity-based encryption over NTRU lattices. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2014: 20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan. Proceedings, Part II 20.","DOI":"10.1007\/978-3-662-45608-8_2"},{"key":"ref_28","unstructured":"Micciancio, D., and Walter, M. (2016, January 8\u201312). Practical, predictable lattice basis reduction. Proceedings of the Advances in Cryptology\u2013EUROCRYPT 2016: 35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria. Proceedings, Part I 35."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Ducas, L., and van Woerden, W. (2021, January 6\u201310). NTRU fatigue: How stretched is overstretched?. Proceedings of the Advances in Cryptology\u2013ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore. Proceedings, Part IV 27.","DOI":"10.1007\/978-3-030-92068-5_1"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/16\/3\/200\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,9]],"date-time":"2025-10-09T16:47:14Z","timestamp":1760028434000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/16\/3\/200"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3,5]]},"references-count":29,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2025,3]]}},"alternative-id":["info16030200"],"URL":"https:\/\/doi.org\/10.3390\/info16030200","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2025,3,5]]}}}