TARU PUBLICATIONS
Journal of Discrete Mathematical Sciences and Cryptography cover

Journal of Discrete Mathematical Sciences and Cryptography

(Since 1998)
Open Access ·Peer-reviewed·ISSN (Online): 2169-0065·ISSN (Print): 0972-0529

CiteScore 2025: 2.7 (Q1)

Powered by:Powered by

Monthly Journal: Publishes theoretical and applied research in all areas of Discrete Mathematical Sciences, Cryptography, Combinatorics, Elliptic Curves and Information Security.

Issues up to 2022 co-published with and available at:Taylor & Francis Online
submissions@tarupublications.com
Taru Online First Current IssueSpecial IssuesBrowse all Issues
Journal of Discrete Mathematical Sciences and Cryptography
Open Access Research Article

Systematic literature review on bootstrapping procedure of FHE schemes

, *

* Corresponding author · click or hover a name for details

pp. 1919–1948Vol. 27Issue 6September 2024DOI: 10.47974/JDMSC-1928 Crossmark XML
Received:
11 Oct 2023
Published Online:
16 Sep 2024
Article type:
Research Article
Language:
EN
Article no.:
JDMSC-1928
Pages:
1919–1948

Abstract

Fully homomorphic encryption is one of the ultimate goals of the cryptography. It is the utmost solution for data privacy. The first seeds of the concept were planted nearly fifty-five years ago. After the thesis of Gentry, first theoretic structure was ready for the researchers. In the following years many different FHE schemes were suggested, and they were vastly improved. FHE schemes have noise or error added to the system in order to make the schemes secure, actually post quantumly secure in some cases. But this noise should be arranged regularly, not to be preponderated over the data. The core mechanism of the FHE is bootstrapping, which regulates the noise and enables us to do homomorphic operations without losing the decryption of plaintext. In this study, we collected research articles from reputable databases and reviewed them. By doing so, we make it easier to keep up with the latest advancements in bootstrapping of FHE schemes. Our goal is to provide a valuable resource for anyone with background seeking to stay up-to-date on the latest developments in the bootstrapping procedure of FHE schemes. Also, we sought answers to our research questions. Lastly, we gave open problems for related studies. 

Keywords

Fully homomorphic encryptionHomomorphic encryptionBootstrapping

Subject Classifications

[2010] Primary 68P25Secondary 11T71

References

[1] A. Acar, H. Aksu, A. S. Uluagac, and M. Conti. A survey on homomorphic encryption schemes: Theory and implementation. ACM Computing Surveys (Csur), 51(4) : 1–35 (2018).
[2] A. Aloufi, P. Hu, Y. Song, and K. Lauter. Computing blindfolded on data homomorphically encrypted under multiple keys: A survey. ACM Computing Surveys (CSUR), 54(9):1–37 (2021).
[3] J. Alperin-Sheriff and C. Peikert. Faster bootstrapping with polynomial error. In Annual Cryptology Conference, pages 297–314. Springer (2014).
[4] S. M. Anggriane, S. M. Nasution, and F. Azmi. Advanced e-voting system using paillier homomorphic encryption algorithm. In 2016 International Conference on Informatics and Computing (ICIC), pages 338–342. IEEE (2016).
[5] K. M. M. Aung, H. T. Lee, B. H. M. Tan, and H. Wang. Fully homomorphic encryption over the integers for non-binary plaintexts without the sparse subset sum problem. Theoretical Computer Science, 771:49–70 (2019).
[6] P. B. Bomolo, E. M. Mukendi, and S. N. Badibanga. Trend of bootstrapping from 2009 to 2016. International Journal of Advanced Computer Science and Applications, 12(12) (2021).
[7] D. Boneh, C. Gentry, S. Halevi, F. Wang, and D. J. Wu. Private database queries using somewhat homomorphic encryption. In International Conference on Applied Cryptography and Network Security, pages 102–118. Springer (2013).
[8] D. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-dnf formulas on ciphertexts. In TCC, volume 3378, pages 325–341. Springer (2005).
[9] C. Bonte, I. Iliashenko, J. Park, H. V. Pereira, and N. P. Smart. Final: Faster fhe instantiated with ntru and lwe. Cryptology ePrint Archive (2022).
[10] J. W. Bos, K. Lauter, J. Loftus, and M. Naehrig. Improved security for a ring-based fully homomorphic encryption scheme. In IMA International Conference on Cryptography and Coding, pages 45–64. Springer (2013).
[11] Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3) : 1–36 (2014).
[12] X. Che, T. Zhou, N. Li, H. Zhou, Z. Chen, and X. Yang. Modified multi-key fully homomorphic encryption based on ntru cryptosystem without key-switching. Tsinghua Science and Technology, 25(5) : 564–578 (2020).
[13] H. Chen and K. Han. Homomorphic lower digits removal and improved fhe bootstrapping. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 315–337. Springer (2018).
[14] J. H. Cheon, J.-S. Coron, J. Kim, M. S. Lee, T. Lepoint, M. Tibouchi, and A. Yun. Batch fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 315–335. Springer (2013).
[15] J. H. Cheon, A. Kim, M. Kim, and Y. Song. Homomorphic encryption for arithmetic of approximate numbers. In International conference on the theory and application of cryptology and information security, pages 409–437. Springer (2017).
[16] J. H. Cheon and D. Stehl´e. Fully homomophic encryption over the integers revisited. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 513–536. Springer, 2015.
[17] I. Chillotti, N. Gama, M. Georgieva, and M. Izabach`ene. Tfhe: fast fully homomorphic encryption over the torus. Journal of Cryptology, 33(1):34–91 (2020).
[18] J.-S. Coron, T. Lepoint, and M. Tibouchi. Scale-invariant fully homomorphic encryption over the integers. In International Workshop on Public Key Cryptography, pages 311–328. Springer (2014).
[19] J.-S. Coron, A. Mandal, D. Naccache, and M. Tibouchi. Fully homomorphic encryption over the integers with shorter public keys. In Annual Cryptology Conference, pages 487–504. Springer (2011).
[20] J.-S. Coron, D. Naccache, and M. Tibouchi. Public key compression and modulus switching for fully homomorphic encryption over the integers. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 446–464. Springer (2012).
[21] R. Cramer, L. Ducas, C. Peikert, and O. Regev. Recovering short generators of principal ideals in cyclotomic rings. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 559–585. Springer (2016).
[22] M. v. Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. In Annual international conference on the theory and applications of cryptographic techniques, pages 24–43. Springer (2010).
[23] L. Ducas and D. Micciancio. Fhew: bootstrapping homomorphic encryption in less than a second. In Advances in Cryptology–EUROCRYPT 2015: 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I 34, pages 617–640. Springer (2015).
[24] T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE transactions on information theory, 31(4):469–472 (1985).
[25] C. Gentry. A fully homomorphic encryption scheme. Stanford university (2009).
[26] C. Gentry and S. Halevi. Implementing gentry’s fully-homomorphic encryption scheme. In Annual international conference on the theory and applications of cryptographic techniques, pages 129–148. Springer (2011).
[27] C. Gentry, A. Sahai, and B. Waters. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. In Annual Cryptology Conference, pages 75–92. Springer (2013).
[28] E. Giurgea, T. Hutu, and E. Simion. Some practical applications of fully homomorphic encryption. Cryptology ePrint Archive (2023).
[29] S. Halevi and V. Shoup. Bootstrapping for helib. Journal of Cryptology, 34(1) : 1–44 (2021).
[30] K. Han, M. Hhan, and J. H. Cheon. Improved homomorphic discrete fourier transforms and fhe bootstrapping. IEEE Access, 7 : 57361–57370 (2019).
[31] K. Han and D. Ki. Better bootstrapping for approximate homomorphic encryption. In Topics in Cryptology–CT-RSA 2020: The Cryptographers’ Track at the RSA Conference 2020, San Francisco, CA, USA, February 24–28, 2020, Proceedings, pages 364–390. Springer (2020).
[32] R. Hiromasa, M. Abe, and T. Okamoto. Packing messages and optimizing bootstrapping in gsw-fhe. IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences, 99(1) : 73–82 (2016).
[33] J. Hoffstein, J. Pipher, and J. H. Silverman. Ntru: A ring-based public key cryptosystem. In International algorithmic number theory symposium, pages 267–288. Springer (1998).
[34] N. Howgrave-Graham. Approximate integer common divisors. In International Cryptography and Lattices Conference, pages 51–66. Springer (2001).
[35] Y. Ishai and A. Paskin. Evaluating branching programs on encrypted data. In Theory of Cryptography: 4th Theory of Cryptography Conference, TCC 2007, Amsterdam, The Netherlands, February 21-24, 2007. Proceedings 4, pages 575–594. Springer (2007).
[36] C. Kavitha and B. Harsoor. A survey on homomorphic encryption in cloud security. International Journal of Engineering and Technology (UAE), 7(4) : 71–74 (2018).
[37] F. Kitagawa and T. Matsuda. Circular security is complete for kdm security. In International Conference on the Theory and Application of Cryptology and Information Security, pages 253–285. Springer (2020).
[38] K. Kluczniak. Ntru-nm: Secure fully homomorphic encryption from ntru with small modulus. Cryptology ePrint Archive (2022).
[39] B. S. Latibari, K. I. Gubbi, H. Homayoun, and A. Sasan. A survey on fhe acceleration. In 2023 IEEE 16th Dallas Circuits and Systems Conference (DCAS), pages 1–6. IEEE (2023).
[40] J.-W. Lee, H. Kang, Y. Lee, W. Choi, J. Eom, M. Deryabin, E. Lee, J. Lee, D. Yoo, Y.-S. Kim, et al. Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access, 10:30039–30054 (2022).
[41] Y. Lee, J.-W. Lee, Y.-S. Kim, and J.-S. No. Near-optimal polynomial for modulus reduction using l2-norm for approximate homomorphic encryption. IEEE Access, 8:144321–144330 (2020).
[42] N. Li, T. Zhou, X. Yang, Y. Han, and Y. Sun. Efficient fully homomorphic encryption with large plaintext space. IETE Technical Review, 35(sup1) : 85–96 (2018).
[43] Z. Lian, Y. Hu, H. Chen, and B. Wang. Bootstrapping of fhe over the integers with large message space. Security and Communication Networks, 2018 (2018).
[44] A. L´opez-Alt, E. Tromer, and V. Vaikuntanathan. On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1219–1234 (2012).
[45] C. Marcolla, V. Sucasas, M. Manzano, R. Bassoli, F. H. Fitzek, and N. Aaraj. Survey on fully homomorphic encryption, theory, and applications. Proceedings of the IEEE, 110(10):1572–1609 (2022).
[46] P. Martins, L. Sousa, and A. Mariano. A survey on fully homomorphic encryption: An engineering perspective. ACM Computing Surveys (CSUR), 50(6) : 1–33 (2017).
[47] M. Naehrig, K. Lauter, and V. Vaikuntanathan. Can homomorphic encryption be practical? In Proceedings of the 3rd ACM workshop on Cloud computing security workshop, pages 113–124 (2011).
[48] K. Nuida and K. Kurosawa. (batch) fully homomorphic encryption over integers for nonbinary message spaces. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 537–555. Springer (2015).
[49] H. Okada, S. Kiyomoto, and C. Cid. Integer-wise functional bootstrapping on tfhe: Applications in secure integer arithmetics. Information, 12(8) : 297 (2021).
[50] P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. In International conference on the theory and applications of cryptographic techniques, pages 223–238. Springer (1999).
[51] J. Park, D. S. Kim, and H. Lim. Privacy-preserving reinforcement learning using homomorphic encryption in cloud computing infrastructures. IEEE Access, 8 : 203564–203579 (2020).
[52] H. V. L. Pereira. Bootstrapping fully homomorphic encryption over the integers in less than one second. In IACR International Conference on Public-Key Cryptography, pages 331–359. Springer (2021).
[53] R. Podschwadt, D. Takabi, P. Hu, M. H. Rafiei, and Z. Cai. A survey of deep learning architectures for privacy-preserving machine learning with fully homomorphic encryption. IEEE Access, 10:117477–117500 (2022).
[54] X. Qin, R. Huang, and H. Fan. An effective ntru-based fully homomorphic encryption scheme. Mathematical Problems in Engineering, 2021 (2021).
[55] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6) : 1–40 (2009).
[56] R. L. Rivest, L. Adleman, M. L. Dertouzos, et al. On data banks and privacy homomorphisms. Foundations of secure computation, 4(11) : 169–180 (1978).
[57] R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 21(2) : 120–126 (1978).
[58] P. W. Shor. Algorithms for quantum computation: discrete logarithms and factoring. In Proceedings 35th annual symposium on foundations of computer science, pages 124–134. Ieee (1994).
[59] A. Silverberg. Fully homomorphic encryption for mathematicians. Women in Numbers 2: Research Directions in Number Theory, 606 : 111 (2013).
[60] W.-T. Song, B. Hu, and X.-F. Zhao. Privacy protection of iot based on fully homomorphic encryption. Wireless Communications and Mobile Computing, 2018 (2018).
[61] B. Wang, X. Wang, R. Xue, and X. Huang. Matrix fhe and its application in optimizing bootstrapping. The Computer Journal, 61(12):1845–1861 (2018).
[62] H. Wang and Q. Tang. Efficient homomorphic integer polynomial evaluation based on gsw fhe. The Computer Journal, 61(4) : 575–585 (2018).
[63] Y. Yang, X. Huang, X. Liu, H. Cheng, J. Weng, X. Luo, and V. Chang. A comprehensive survey on secure outsourced computation and its applications. IEEE Access, 7:159426–159465 (2019).
[64] Q. Zhang, L. T. Yang, Z. Chen, P. Li, and M. J. Deen. Privacy-preserving double-projection deep computation model with crowdsourcing on cloud for big data feature learning. IEEE Internet of Things Journal, 5(4) : 2896–2903 (2017).
[65] F. Zhao, C. Li, and C. F. Liu. A cloud computing security solution based on fully homomorphic encryption. In 16th international conference on advanced communication technology, pages 485–488. IEEE (2014).
[66] X. Zhao, H. Mao, S. Liu, W. Song, and B. Zhang. Analysis on matrix gsw-fhe and optimizing bootstrapping. Security and Communication Networks, 2018 (2018).
[67] X. Zhao and A. Wang. Generalized bootstrapping technique based on block equality test algorithm. Security and Communication Networks, 2018 (2018).
[68] T. Zhou, X. Yang, L. Liu, W. Zhang, and N. Li. Faster bootstrapping with multiple addends. IEEE Access, 6 : 49868–49876 (2018).

Views: 354Downloads: 111Citations: 0