{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T16:19:18Z","timestamp":1783009158899,"version":"3.54.5"},"publisher-location":"Cham","reference-count":61,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031587221","type":"print"},{"value":"9783031587238","type":"electronic"}],"license":[{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,1,1]],"date-time":"2024-01-01T00:00:00Z","timestamp":1704067200000},"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":[[2024]]},"DOI":"10.1007\/978-3-031-58723-8_4","type":"book-chapter","created":{"date-parts":[[2024,5,7]],"date-time":"2024-05-07T12:01:49Z","timestamp":1715083309000},"page":"94-123","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":30,"title":["Bootstrapping Bits with\u00a0CKKS"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-6870-4504","authenticated-orcid":false,"given":"Youngjin","family":"Bae","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7085-2220","authenticated-orcid":false,"given":"Jung Hee","family":"Cheon","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1624-6326","authenticated-orcid":false,"given":"Jaehyung","family":"Kim","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3435-2453","authenticated-orcid":false,"given":"Damien","family":"Stehl\u00e9","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2024,5,8]]},"reference":[{"key":"4_CR1","unstructured":"Aharoni, E., Drucker, N., Ezov, G., Kushnir, E., Shaul, H., Soceanu, O.: E2E near-standard and practical authenticated transciphering. Cryptology ePrint Archive, Paper 2023\/1040 (2023)"},{"key":"4_CR2","unstructured":"Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. (2015). Software available at https:\/\/github.com\/malb\/lattice-estimator (commit fd4a460)"},{"key":"4_CR3","unstructured":"Al Badawi, A., et al.: OpenFHE: open-source fully homomorphic encryption library. Cryptology ePrint Archive, Paper 2022\/915 (2022). Software available at https:\/\/github.com\/openfheorg\/openfhe-development (commit 4ebb28e)"},{"key":"4_CR4","doi-asserted-by":"crossref","unstructured":"Bae, Y., Cheon, J.H., Cho, W., Kim, J., Kim, T.: META-BTS: bootstrapping precision beyond the limit. In: CCS (2022)","DOI":"10.1145\/3548606.3560696"},{"key":"4_CR5","doi-asserted-by":"crossref","unstructured":"Bae, Y., Cheon, J.H., Kim, J., Park, J.H., Stehl\u00e9, D.: HERMES: efficient ring packing using MLWE ciphertexts and application to transciphering. In: CRYPTO (2023)","DOI":"10.1007\/978-3-031-38551-3_2"},{"key":"4_CR6","doi-asserted-by":"crossref","unstructured":"Boura, C., Gama, N., Georgieva, M., Jetchev, D.: CHIMERA: combining ring-LWE-based fully homomorphic encryption schemes. J. Math. Cryptol. (2020)","DOI":"10.1515\/jmc-2019-0026"},{"key":"4_CR7","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: ITCS (2012)","DOI":"10.1145\/2090236.2090262"},{"key":"4_CR8","doi-asserted-by":"crossref","unstructured":"Bonte, C., Iliashenko, I., Park, J., Pereira, H.V.L., Smart, N.P.: FINAL: faster FHE instantiated with NTRU and LWE. In: ASIACRYPT (2022)","DOI":"10.1007\/978-3-031-22966-4_7"},{"key":"4_CR9","doi-asserted-by":"crossref","unstructured":"Bossuat, J.-P., Mouchet, C., Troncoso-Pastoriza, J., Hubaux, J.-P.: Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys. In: EUROCRYPT (2021)","DOI":"10.1007\/978-3-030-77870-5_21"},{"key":"4_CR10","unstructured":"Al Badawi, A., Polyakov, Y.: Demystifying bootstrapping in fully homomorphic encryption. Cryptology ePrint Archive, Paper 2023\/149 (2023)"},{"key":"4_CR11","doi-asserted-by":"crossref","unstructured":"Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical GapSVP. In: CRYPTO (2012)","DOI":"10.1007\/978-3-642-32009-5_50"},{"key":"4_CR12","doi-asserted-by":"crossref","unstructured":"Bossuat, J.-P., Troncoso-Pastoriza, J., Hubaux, J.-P.: Bootstrapping for approximate homomorphic encryption with negligible failure-probability by using sparse-secret encapsulation. In: ACNS (2022)","DOI":"10.1007\/978-3-031-09234-3_26"},{"key":"4_CR13","doi-asserted-by":"crossref","unstructured":"Chen, H., Chillotti, I., Song, Y.: Improved bootstrapping for approximate homomorphic encryption. In: EUROCRYPT (2019)","DOI":"10.1007\/978-3-030-17656-3_2"},{"key":"4_CR14","doi-asserted-by":"crossref","unstructured":"Chen, H., Dai, W., Kim, M., Song, Y.: Efficient homomorphic conversion between (ring) LWE ciphertexts. In: ACNS (2021)","DOI":"10.1007\/978-3-030-78372-3_18"},{"key":"4_CR15","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., Georgieva, M., Izabach\u00e8ne, M.: Faster fully homomorphic encryption: bootstrapping in less than 0.1 seconds. In: ASIACRYPT (2016)","DOI":"10.1007\/978-3-662-53887-6_1"},{"key":"4_CR16","unstructured":"Chillotti, I., Gama, N., Georgieva, M., Izabach\u00e8ne, M.: TFHE: fast fully homomorphic encryption library (version\u00a01.1) (2016). Software available at https:\/\/tfhe.github.io\/tfhe\/"},{"key":"4_CR17","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Gama, N., Georgieva, M., Izabach\u00e8ne, M.: Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. In: ASIACRYPT (2017)","DOI":"10.1007\/978-3-319-70694-8_14"},{"key":"4_CR18","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: Bootstrapping for approximate homomorphic encryption. In: EUROCRYPT (2018)","DOI":"10.1007\/978-3-319-78381-9_14"},{"key":"4_CR19","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: A full RNS variant of approximate homomorphic encryption. In: SAC (2018)","DOI":"10.1007\/978-3-030-10970-7_16"},{"key":"4_CR20","doi-asserted-by":"crossref","unstructured":"Cho, J., et al.: Transciphering framework for approximate homomorphic encryption. In: ASIACRYPT (2021)","DOI":"10.1007\/978-3-030-92078-4_22"},{"key":"4_CR21","doi-asserted-by":"crossref","unstructured":"Carpov, S., Izabach\u00e8ne, M., Mollimard, V.: New techniques for multi-value input homomorphic evaluation and applications. In: CT-RSA (2019)","DOI":"10.1007\/978-3-030-12612-4_6"},{"key":"4_CR22","unstructured":"Chillotti, I., Joye, M., Ligier, D., Orfila, J.-B., Tap, S.: Concrete: concrete operates on ciphertexts rapidly by extending TFHE. In: WAHC (2020)"},{"key":"4_CR23","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Joye, M., Paillier, P.: Programmable bootstrapping enables efficient homomorphic inference of deep neural networks. In: CSCML (2021)","DOI":"10.1007\/978-3-030-78086-9_1"},{"key":"4_CR24","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Kim, D., Kim, D.: Efficient homomorphic comparison methods with optimal complexity. In: ASIACRYPT (2020)","DOI":"10.1007\/978-3-030-64834-3_8"},{"key":"4_CR25","doi-asserted-by":"crossref","unstructured":"Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: ASIACRYPT (2017)","DOI":"10.1007\/978-3-319-70694-8_15"},{"key":"4_CR26","doi-asserted-by":"crossref","unstructured":"Chillotti, I., Ligier, D., Orfila, J.-B., Tap, S.: Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE. In: ASIACRYPT (2021)","DOI":"10.1007\/978-3-030-92078-4_23"},{"key":"4_CR27","unstructured":"CryptoLab. HEaaN library (2022). https:\/\/www.cryptolab.co.kr\/en\/products-en\/heaan-he\/"},{"key":"4_CR28","doi-asserted-by":"crossref","unstructured":"Ducas, L., Micciancio, D.: FHEW: bootstrapping homomorphic encryption in less than a second. In: EUROCRYPT (2015)","DOI":"10.1007\/978-3-662-46800-5_24"},{"key":"4_CR29","doi-asserted-by":"crossref","unstructured":"Drucker, N., Moshkowich, G., Pelleg, T., Shaul, H.: BLEACH: cleaning errors in discrete computations over CKKS. J. Cryptol. (2024)","DOI":"10.1007\/s00145-023-09483-1"},{"key":"4_CR30","unstructured":"EPFL-LDS, Tune Insight SA. Lattigo v4 (2022). https:\/\/github.com\/tuneinsight\/lattigo"},{"key":"4_CR31","unstructured":"Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Paper 2012\/144 (2012)"},{"key":"4_CR32","doi-asserted-by":"crossref","unstructured":"Guimar\u00e3es, A., Borin, E., Aranha, D.F.: Revisiting the functional bootstrap in TFHE. IACR Trans. Cryptogr. Hardw. Embed. Syst. (2021)","DOI":"10.46586\/tches.v2021.i2.229-253"},{"key":"4_CR33","doi-asserted-by":"crossref","unstructured":"Gentry, C., Halevi, S., Peikert, C., Smart, N.P.: Field switching in BGV-style homomorphic encryption. J. Comput. Secur. (2013)","DOI":"10.1007\/978-3-642-32928-9_2"},{"key":"4_CR34","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\/14 (2023)","DOI":"10.1007\/978-981-99-8736-8_1"},{"key":"4_CR35","doi-asserted-by":"crossref","unstructured":"Harvey, D.: Faster arithmetic for number-theoretic transforms. J. Symb. Comput. (2014)","DOI":"10.1016\/j.jsc.2013.09.002"},{"key":"4_CR36","doi-asserted-by":"crossref","unstructured":"Han, K., Ki, D.: Better bootstrapping for approximate homomorphic encryption. In: CT-RSA (2020)","DOI":"10.1007\/978-3-030-40186-3_16"},{"key":"4_CR37","doi-asserted-by":"crossref","unstructured":"Halevi, S., Shoup, V.: Algorithms in HElib. In: CRYPTO (2014)","DOI":"10.1007\/978-3-662-44371-2_31"},{"key":"4_CR38","unstructured":"Jutla, C.S., Manohar, N.: Modular Lagrange interpolation of the mod function for bootstrapping of approximate HE. Cryptology ePrint Archive, Paper 2020\/1355 (2020)"},{"key":"4_CR39","doi-asserted-by":"crossref","unstructured":"Jutla, C.S., Manohar, N.: Sine series approximation of the mod function for bootstrapping of approximate HE. In: EUROCRYPT (2022)","DOI":"10.1007\/978-3-031-06944-4_17"},{"key":"4_CR40","doi-asserted-by":"crossref","unstructured":"Kim, M., Lee, D., Seo, J., Song, Y.: Accelerating HE operations from key decomposition technique. In: CRYPTO (2023)","DOI":"10.1007\/978-3-031-38551-3_3"},{"key":"4_CR41","unstructured":"Kluczniak, K.: NTRU-$$\\nu $$-um: secure fully homomorphic encryption from NTRU with small modulus. In: CCS (2022)"},{"key":"4_CR42","doi-asserted-by":"crossref","unstructured":"Kluczniak, K., Schild, L.: FDFB: full domain functional bootstrapping towards practical fully homomorphic encryption. IACR Trans. Cryptogr. Hardw. Embed. Syst. (2023)","DOI":"10.46586\/tches.v2023.i1.501-537"},{"key":"4_CR43","doi-asserted-by":"crossref","unstructured":"Kim, J., Seo, J., Song, Y.: Simpler and faster BFV bootstrapping for arbitrary plaintext modulus from CKKS. Cryptology ePrint Archive, Paper 2024\/109 (2024)","DOI":"10.1145\/3658644.3670302"},{"key":"4_CR44","doi-asserted-by":"crossref","unstructured":"Lu, W.-J., Huang, Z., Hong, C., Ma, Y., Qu, H.: PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption. In: S &P (2021)","DOI":"10.1109\/SP40001.2021.00043"},{"key":"4_CR45","doi-asserted-by":"crossref","unstructured":"Lee, Y., Lee, J.-W., Kim, Y.-S., Kim, Y., No, J.-S., Kang, H.: High-precision bootstrapping for approximate homomorphic encryption by error variance minimization. In: EUROCRYPT (2022)","DOI":"10.1007\/978-3-031-06944-4_19"},{"key":"4_CR46","doi-asserted-by":"crossref","unstructured":"Lee, Y., Lee, J.-W., Kim, Y.-S., No, J.-S.: Near-optimal polynomial for modulus reduction using L2-norm for approximate homomorphic encryption. IEEE Access (2020)","DOI":"10.1109\/ACCESS.2020.3014369"},{"key":"4_CR47","doi-asserted-by":"crossref","unstructured":"Lee, J.-W., Lee, E., Lee, Y., Kim, Y.-S., No, J.-S.: High-precision bootstrapping of RNS-CKKS homomorphic encryption using optimal minimax polynomial approximation and inverse sine function. In: UROCRYPT (2021)","DOI":"10.1007\/978-3-030-77870-5_22"},{"key":"4_CR48","doi-asserted-by":"crossref","unstructured":"Lee, Y., et al.: Efficient FHEW bootstrapping with small evaluation keys, and applications to threshold homomorphic encryption. In: EUROCRYPT (2023)","DOI":"10.1007\/978-3-031-30620-4_8"},{"key":"4_CR49","doi-asserted-by":"crossref","unstructured":"Lee, C., Min, S., Seo, J., Song, Y.: Faster TFHE bootstrapping with block binary keys. In: AsiaCCS (2023)","DOI":"10.1145\/3579856.3595804"},{"key":"4_CR50","doi-asserted-by":"crossref","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: EUROCRYPT (2010)","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"4_CR51","doi-asserted-by":"crossref","unstructured":"Liu, F.-H., Wang, H.: Batch bootstrapping I: a new framework for SIMD bootstrapping in polynomial modulus. In: EUROCRYPT (2023)","DOI":"10.1007\/978-3-031-30620-4_11"},{"key":"4_CR52","doi-asserted-by":"crossref","unstructured":"Liu, F.-H., Wang, H.: Batch bootstrapping II: bootstrapping in polynomial modulus only requires $$\\widetilde{O}(1)$$ FHE multiplications in amortization. In: EUROCRYPT (2023)","DOI":"10.1007\/978-3-031-30620-4_12"},{"key":"4_CR53","doi-asserted-by":"crossref","unstructured":"Liu, Z., Wang, Y.: Amortized functional bootstrapping in less than 7\u00a0ms, with $$\\tilde{O}(1)$$ polynomial multiplications. In: ASIACRYPT (2023)","DOI":"10.1007\/978-981-99-8736-8_4"},{"key":"4_CR54","doi-asserted-by":"crossref","unstructured":"Liu, Z., Wang, Y.: Relaxed functional bootstrapping: a new perspective on BGV\/BFV bootstrapping. Cryptology ePrint Archive, Paper 2024\/172 (2024)","DOI":"10.1007\/978-981-96-0875-1_7"},{"key":"4_CR55","doi-asserted-by":"crossref","unstructured":"Ma, S., Huang, T., Wang, A., Wang, X.: Accelerating BGV bootstrapping for large $$p$$ using null polynomials over $$\\mathbb{Z}_{p^e}$$. Cryptology ePrint Archive, Paper 2024\/115, to appear in the proceedings of EUROCRYPT\u201924 (2024)","DOI":"10.1007\/978-3-031-58723-8_14"},{"key":"4_CR56","doi-asserted-by":"crossref","unstructured":"De Micheli, G., Kim, D., Micciancio, D., Suhl, A.: Faster amortized FHEW bootstrapping using ring automorphisms. Cryptology ePrint Archive, Paper 2023\/112 (2023)","DOI":"10.1007\/978-3-031-57728-4_11"},{"key":"4_CR57","unstructured":"Micciancio, D., Sorrell, J.: Ring packing and amortized FHEW bootstrapping. In: ICALP (2018)"},{"key":"4_CR58","doi-asserted-by":"crossref","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC (2005)","DOI":"10.1145\/1060590.1060603"},{"key":"4_CR59","doi-asserted-by":"crossref","unstructured":"Stehl\u00e9, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: ASIACRYPT (2009)","DOI":"10.1007\/978-3-642-10366-7_36"},{"key":"4_CR60","doi-asserted-by":"crossref","unstructured":"Trama, D., Clet, P.-E., Boudguiga, A., Sirdey, R.: At last! a homomorphic AES evaluation in less than 30 seconds by means of TFHE. Cryptology ePrint Archive, Paper 2023\/1020 (2023)","DOI":"10.1145\/3605759.3625260"},{"key":"4_CR61","doi-asserted-by":"crossref","unstructured":"Xiang, B., Zhang, J., Deng, Y., Dai, Y., Feng, D.: Fast blind rotation for bootstrapping FHEs. In: CRYPTO (2023)","DOI":"10.1007\/978-3-031-38551-3_1"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2024"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-58723-8_4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,7]],"date-time":"2026-05-07T01:23:54Z","timestamp":1778117034000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-58723-8_4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024]]},"ISBN":["9783031587221","9783031587238"],"references-count":61,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-58723-8_4","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024]]},"assertion":[{"value":"8 May 2024","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Zurich","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Switzerland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 May 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30 May 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"43","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}