{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,7]],"date-time":"2026-04-07T18:05:33Z","timestamp":1775585133628,"version":"3.50.1"},"publisher-location":"Singapore","reference-count":41,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819987351","type":"print"},{"value":"9789819987368","type":"electronic"}],"license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2023]]},"DOI":"10.1007\/978-981-99-8736-8_4","type":"book-chapter","created":{"date-parts":[[2023,12,17]],"date-time":"2023-12-17T06:01:54Z","timestamp":1702792914000},"page":"101-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":26,"title":["Amortized Functional Bootstrapping in\u00a0Less than 7 ms, with\u00a0$$\\tilde{O}(1)$$ Polynomial Multiplications"],"prefix":"10.1007","author":[{"given":"Zeyu","family":"Liu","sequence":"first","affiliation":[]},{"given":"Yunhao","family":"Wang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,12,18]]},"reference":[{"key":"4_CR1","unstructured":"Albrecht, M., Chase, M., Chen, H., et al.: Homomorphic encryption security standard. Tech. rep., HomomorphicEncryption.org, Toronto, Canada (2018)"},{"key":"4_CR2","doi-asserted-by":"publisher","unstructured":"Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169\u2013203 (2015). https:\/\/doi.org\/10.1515\/jmc-2015-0016","DOI":"10.1515\/jmc-2015-0016"},{"key":"4_CR3","doi-asserted-by":"crossref","unstructured":"Alperin-Sheriff, J., Peikert, C.: Practical bootstrapping in quasilinear time, pp. 1\u201320 (2013)","DOI":"10.1007\/978-3-642-40041-4_1"},{"key":"4_CR4","unstructured":"Badawi, A.A., et al.: OpenFHE: open-source fully homomorphic encryption library. Cryptology ePrint Archive, Paper 2022\/915 (2022). https:\/\/eprint.iacr.org\/2022\/915. commit: 122f470e0dbf94688051ab852131ccc5d26be934"},{"key":"4_CR5","doi-asserted-by":"publisher","unstructured":"Boura, C., Gama, N., Georgieva, M., Jetchev, D.: CHIMERA: combining ring-LWE-based fully homomorphic encryption schemes. J. Math. Cryptol. 14(1), 316\u2013338 (2020). https:\/\/doi.org\/10.1515\/jmc-2019-0026","DOI":"10.1515\/jmc-2019-0026"},{"key":"4_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"868","DOI":"10.1007\/978-3-642-32009-5_50","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"Z Brakerski","year":"2012","unstructured":"Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical GapSVP. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 868\u2013886. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32009-5_50"},{"issue":"3","key":"4_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2633600","volume":"6","author":"Z Brakerski","year":"2014","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theory (TOCT) 6(3), 1\u201336 (2014)","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Chen, H., Han, K.: Homomorphic lower digits removal and improved FHE bootstrapping (2018)","DOI":"10.1007\/978-3-319-78381-9_12"},{"key":"4_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"360","DOI":"10.1007\/978-3-319-78381-9_14","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"JH Cheon","year":"2018","unstructured":"Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: Bootstrapping for approximate homomorphic encryption. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 360\u2013384. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_14"},{"key":"4_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"409","DOI":"10.1007\/978-3-319-70694-8_15","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2017","author":"JH Cheon","year":"2017","unstructured":"Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10624, pp. 409\u2013437. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70694-8_15"},{"key":"4_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-53887-6_1","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2016","author":"I Chillotti","year":"2016","unstructured":"Chillotti, I., Gama, N., Georgieva, M., Izabach\u00e8ne, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 3\u201333. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53887-6_1"},{"key":"4_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"670","DOI":"10.1007\/978-3-030-92078-4_23","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2021","author":"I Chillotti","year":"2021","unstructured":"Chillotti, I., Ligier, D., Orfila, J.-B., Tap, S.: Improved programmable bootstrapping with\u00a0larger precision and\u00a0efficient arithmetic circuits for\u00a0TFHE. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13092, pp. 670\u2013699. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-92078-4_23"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Cong, K., et al.: Labeled PSI from homomorphic encryption with reduced computation and communication. In: Proceedings of the 2021 ACM SIGSAC Conference on Computer and Communications Security. CCS 2021, Association for Computing Machinery (2021)","DOI":"10.1145\/3460120.3484760"},{"key":"4_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1007\/978-3-662-46800-5_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2015","author":"L Ducas","year":"2015","unstructured":"Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 617\u2013640. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46800-5_24"},{"key":"4_CR15","first-page":"144","volume":"2012","author":"J Fan","year":"2012","unstructured":"Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. IACR Cryptol. ePrint Arch. 2012, 144 (2012)","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"4_CR16","doi-asserted-by":"crossref","unstructured":"Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 169\u2013178 (2009)","DOI":"10.1145\/1536414.1536440"},{"key":"4_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1007\/978-3-642-32928-9_2","volume-title":"Security and Cryptography for Networks","author":"C Gentry","year":"2012","unstructured":"Gentry, C., Halevi, S., Peikert, C., Smart, N.P.: Ring switching in BGV-Style homomorphic encryption. In: Visconti, I., De Prisco, R. (eds.) SCN 2012. LNCS, vol. 7485, pp. 19\u201337. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32928-9_2"},{"key":"4_CR18","doi-asserted-by":"publisher","unstructured":"Guimar\u00e3es, A., Borin, E., Aranha, D.F.: Revisiting the functional bootstrap in TFHE. IACR Trans. Cryptograph. Hardware Embedded Syst. 2021, 229\u2013253 (2021). https:\/\/doi.org\/10.46586\/tches.v2021.i2.229-253. https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/view\/8793","DOI":"10.46586\/tches.v2021.i2.229-253"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Guimar\u00e3es, A., Pereira, H.V.L., van Leeuwen, B.: Amortized bootstrapping revisited: simpler, asymptotically-faster, implemented. Cryptology ePrint Archive, Paper 2023\/014 (2023). https:\/\/eprint.iacr.org\/2023\/014","DOI":"10.1007\/978-981-99-8736-8_1"},{"key":"4_CR20","unstructured":"Halevi, S., Shoup, V.: Bootstrapping for HElib. Cryptology ePrint Archive, Report 2014\/873 (2014). https:\/\/eprint.iacr.org\/2014\/873"},{"key":"4_CR21","unstructured":"Halevi, S., Shoup, V.: Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Report 2020\/1481 (2020). https:\/\/eprint.iacr.org\/2020\/1481"},{"key":"4_CR22","doi-asserted-by":"crossref","unstructured":"Iliashenko, I., N\u00e8gre, C., Zucca, V.: Integer functions suitable for homomorphic encryption over finite fields. Cryptology ePrint Archive, Report 2021\/1335 (2021). WAHC 2021","DOI":"10.1145\/3474366.3486925"},{"key":"4_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-030-92078-4_21","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2021","author":"A Kim","year":"2021","unstructured":"Kim, A., Polyakov, Y., Zucca, V.: Revisiting homomorphic encryption schemes for finite fields. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13092, pp. 608\u2013639. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-92078-4_21"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Kluczniak, K., Schild, L.: FDFB: full domain functional bootstrapping towards practical fully homomorphic encryption. IACR Trans. Cryptograph. Hardware Embedd. Syst. 2023(1), 501\u2013537 (2022). https:\/\/tches.iacr.org\/index.php\/TCHES\/article\/view\/9960","DOI":"10.46586\/tches.v2023.i1.501-537"},{"key":"4_CR25","doi-asserted-by":"publisher","unstructured":"Lee, Y., et al.: Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology - EUROCRYPT 2023, pp. 227\u2013256. Springer, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30620-4_8","DOI":"10.1007\/978-3-031-30620-4_8"},{"key":"4_CR26","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-031-30620-4_11","volume-title":"Advances in Cryptology - EUROCRYPT 2023","author":"FH Liu","year":"2023","unstructured":"Liu, F.H., Wang, H.: Batch bootstrapping I: A new framework for SIMD bootstrapping in polynomial modulus. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology - EUROCRYPT 2023, pp. 321\u2013352. Springer Nature Switzerland, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30620-4_11"},{"key":"4_CR27","doi-asserted-by":"publisher","unstructured":"Liu, F.H., Wang, H.: Batch bootstrapping I: Bootstrapping in polynomial modulus only requires $$\\tilde{O}(1)$$ FHE multiplications in amortization. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology - EUROCRYPT 2023, pp. 321\u2013352. Springer Nature Switzerland, Cham (2023). https:\/\/doi.org\/10.1007\/978-3-031-30620-4_12","DOI":"10.1007\/978-3-031-30620-4_12"},{"key":"4_CR28","unstructured":"Liu, K., Xu, C., Dou, B., Xu, L.: Optimization of functional bootstrap with large LUT and packing key switching. Cryptology ePrint Archive, Paper 2023\/631 (2023). https:\/\/eprint.iacr.org\/2023\/631"},{"key":"4_CR29","doi-asserted-by":"publisher","unstructured":"Liu, Z., Micciancio, D., Polyakov, Y.: Large-precision homomorphic sign evaluation using FHEW\/TFHE bootstrapping. In: Advances in Cryptology - ASIACRYPT 2022: 28th International Conference on the Theory and Application of Cryptology and Information Security, Taipei, Taiwan, 5\u20139 December 2022, Proceedings, Part II, pp. 130\u2013160. Springer, Heidelberg (2023). https:\/\/doi.org\/10.1007\/978-3-031-22966-4_5","DOI":"10.1007\/978-3-031-22966-4_5"},{"key":"4_CR30","doi-asserted-by":"crossref","unstructured":"jie Lu, W., Huang, Z., Hong, C., Ma, Y., Qu, H.: PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption. SP 2021 (2020). https:\/\/eprint.iacr.org\/2020\/1606","DOI":"10.1109\/SP40001.2021.00043"},{"key":"4_CR31","unstructured":"Ma, S., Huang, T., Wang, A., Wang, X.: Fast and accurate: efficient full-domain functional bootstrap and digit decomposition for homomorphic computation. Cryptology ePrint Archive, Paper 2023\/645 (2023). https:\/\/eprint.iacr.org\/2023\/645"},{"key":"4_CR32","doi-asserted-by":"publisher","unstructured":"Menon, S.J., Wu, D.J.: Spiral: Fast, high-rate single-server PIR via FHE composition. In: 2022 IEEE Symposium on Security and Privacy (SP), pp. 930\u2013947 (2022). https:\/\/doi.org\/10.1109\/SP46214.2022.9833700","DOI":"10.1109\/SP46214.2022.9833700"},{"key":"4_CR33","doi-asserted-by":"publisher","unstructured":"Micciancio, D., Polyakov, Y.: Bootstrapping in FHEW-like Cryptosystems, pp. 17\u201328. Association for Computing Machinery, New York, NY, USA (2021). https:\/\/doi.org\/10.1145\/3474366.3486924","DOI":"10.1145\/3474366.3486924"},{"key":"4_CR34","unstructured":"Miccianco, D., Sorrell, J.: Ring packing and amortized FHEW bootstrapping. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), vol. 107. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2018)"},{"key":"4_CR35","unstructured":"Micheli, G.D., Kim, D., Micciancio, D., Suhl, A.: Faster amortized FHEW bootstrapping using ring automorphisms. Cryptology ePrint Archive, Paper 2023\/112 (2023). https:\/\/eprint.iacr.org\/2023\/112"},{"key":"4_CR36","unstructured":"PALISADE Lattice Cryptography Library (release 1.11.6). https:\/\/palisade-crypto.org\/ (2022)"},{"issue":"1","key":"4_CR37","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1137\/0202007","volume":"2","author":"MS Paterson","year":"1973","unstructured":"Paterson, M.S., Stockmeyer, L.J.: On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2(1), 60\u201366 (1973)","journal-title":"SIAM J. Comput."},{"key":"4_CR38","unstructured":"Microsoft SEAL (2020). https:\/\/github.com\/Microsoft\/SEAL"},{"key":"4_CR39","unstructured":"Smart, N., Vercauteren, F.: Fully homomorphic SIMD operations. Designs, Codes and Cryptography (2011). https:\/\/eprint.iacr.org\/2011\/133"},{"key":"4_CR40","unstructured":"Zama-AI, THFE-RS (2023). https:\/\/github.com\/zama-ai\/tfhe-rs. commit: 509bf3e2846bc98dd42d0e8eeb7f27852e5b632a"},{"key":"4_CR41","unstructured":"Yang, Z., Xie, X., Shen, H., Chen, S., Zhou, J.: TOTA: fully homomorphic encryption with smaller parameters and stronger security. Cryptology ePrint Archive, Paper 2021\/1347 (2021). https:\/\/eprint.iacr.org\/2021\/1347"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 ASIACRYPT 2023"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-99-8736-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,17]],"date-time":"2025-12-17T01:02:15Z","timestamp":1765933335000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-99-8736-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023]]},"ISBN":["9789819987351","9789819987368"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-981-99-8736-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023]]},"assertion":[{"value":"18 December 2023","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ASIACRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on the Theory and Application of Cryptology and Information Security","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Guangzhou","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2023","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 December 2023","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 December 2023","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"asiacrypt2023","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/asiacrypt.iacr.org\/2023\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"HotCRP","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"375","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"106","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"28% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"12","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}