Abstract
BGV and BFV are among the most widely used fully homomorphic encryption (FHE) schemes, supporting evaluations over a finite field. To evaluate a circuit with arbitrary depth, bootstrapping is needed. However, despite the recent progress, bootstrapping of BGV/BFV still remains relatively impractical, compared to other FHE schemes.
In this work, we inspect the BGV/BFV bootstrapping procedure from a different angle. We provide a generalized bootstrapping definition that relaxes the correctness requirement of regular bootstrapping, allowing constructions that support only certain kinds of circuits with arbitrary depth. In addition, our definition captures a form of functional bootstrapping. In other words, the output encrypts a function evaluation of the input instead of the input itself.
Under this new definition, we provide a bootstrapping procedure supporting different types of functions. Our construction is 1–2 orders of magnitude faster than the state-of-the-art BGV/BFV bootstrapping algorithms, depending on the evaluated function.
Of independent interest, we show that our technique can be used to improve the batched FHEW/TFHE bootstrapping construction introduced by Liu and Wang (Asiacrypt 2023). Our optimization provides a speed-up of 6x in latency and 3x in throughput for binary gate bootstrapping and a plaintext-space-dependent speed-up for functional bootstrapping with plaintext space smaller than \(\mathbb {Z}_{512}\).
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
[u, v] denotes \(\{u, u+1, \dots , v\}\).
- 2.
Each range may contain a different amount of points, but for simplicity here, we assume they all have m points.
- 3.
Can be almost as large as all the other points in \(\mathbb {Z}_t\).
- 4.
Notice that for readability, we use LWE ciphertext as an illustration here, while in the construction, we use RLWE ciphertext instead.
- 5.
- 6.
We focus on BFV in this work, but all our results can be directly transformed to BGV with minimum modification (e.g., with techniques in [3, Sec A]).
- 7.
For \(|\mathcal {Y}| = |[y]| = 1\), a trivial yet valid bootstrapping is to directly output a BFV ciphertext with all slots encrypting y.
- 8.
Let \(f_x^{-1}(y)\) denote a point z where \(f(z) = y\) and \(z - x = \min _{z' \in \mathcal {X}, f(z') = y}(z' - x)\). In other words, \(f_x^{-1}(y)\) outputs a point that is (1) a valid input in \(\mathcal {X}\); and (2) is the close to x among all possible points \(z'\) satisfying \(f(z') = y\).
- 9.
If \(|f_x^{-1}(y_{x,i}) - x| = |f_x^{-1}(y_{x,j}) - x|\) for \(i \ne j\), then any order is accepted.
- 10.
The randomness is taken over the input ciphertext and the generated keys.
- 11.
For simplicity, we assume r divides \(t-1\). This is w.l.o.g because we can make the range \([0, t-t', r]\) where \(t - t'\) is the largest multiple of r with \(t > 0\). This change does not affect the main point or technique of this paper.
- 12.
Note that this is the modulus switching error of the LWE ciphertexts, which we can achieve by simply transforming one RLWE ciphertext to N LWE ciphertexts using the SampleExtract procedure as discussed incite [18]. One may also simply bound the modulus switching error of RLWE as discussed in [37], which is \(O(\sqrt{N})\) for binary/ternary secrets.
- 13.
For simplicity, we assume all possible rotation keys are generated. Later, we discuss how to only generate the necessary ones.
- 14.
Note that if \(|[u, v, r']| < \frac{t-1}{r}\), we can either pad dummy elements to follow the same bootstrapping procedure or apply a more efficient way, introduced in Sect. 5.1.
- 15.
Note that even if we do have an identity mapping (i.e., \(\mathcal {Y}= [u, v, r']\)), the \(f_\textsf{post}\) in the previous section is not enough as we need to revert the influence of \(f_\textsf{pre}\).
- 16.
Note that both our asymptotic behavior and the one in prior works shown in Table 1 assumes using the Paterson-Stockmeyer algorithm discussed in Algorithm 3.
- 17.
Note that if \(y = y'\), the construction is trivial. Simply return \(\textsf{Enc}({\textsf{sk}}, y)\) suffices, as the correctness definition does not explicitly define the behavior for f(x) if \(x \not \in \{z, z'\}\).
- 18.
Recall that \(r = O(\sqrt{h})\) where h is the hamming weight of the secret key.
- 19.
Technically speaking, since it is \((a_i - r/2, b_i + r/2)\), it only has \(|\mathcal {X}| + k(r-1)\) roots. However, it is distracting to either make the range check non-symmetric (i.e., change to \((a_i - r/2, b_i + r/2]\)) or calculate the number of roots more exactly (i.e., \(k(r-1)\) instead of kr). Therefore, for here and also the rest of the paper, we estimate the number of roots roughly for better readability.
- 20.
Notice that \(f_\textsf{ub}\) is a special case of this construction, as for \(f_\textsf{ub}\) in Sect. 5.2, \(h(m) = y_1 - y_2\) is simply a constant function and thus does not require any evaluation. Therefore, the cost is \(S_1 + r + \log (t)\) for \(f_\textsf{ub}\) instead of \(2S_1 + 2r + \log (t)\).
- 21.
Our construction replies on sparse keys in the same way as prior works. We can extend our key to be uniform, but \(r\) needs to be increased accordingly, since \(r = O(\sqrt{h})\) for h being the hamming weight.
- 22.
We choose security parameter \(\delta = 40\) which is the same as in [50], since the error probability is statistical, and 40 is a relatively popular and reasonable statistical security parameter. Prior works in BGV/BFV bootstrapping instead choose error probability via evaluation: based on our private communication with the authors of the prior works, it was chosen such that no overflow happens during benchmarking tests. To our knowledge, other BFV bootstrapping works do not explicitly discuss how they choose the concrete numbers, and thus we follow the parameter in [50]. Asymptotically, \(r = O(\sqrt{\delta })\) when fixing other parameters.
- 23.
According to [15], \(2^{-40}\) gives \({\sim }50\)-bit of security for IND-CPA-D (introduced in [46]). To achieve 128-bit security of IND-CPA-D, roughly a failure probability of \(2^{-120}\) is needed. To accommodate this, our error range grows from 128 to \({\sim }216\) and thus the effective plaintext space (for \(f_1, f_2\)) is reduced from 512 points to \({\sim }302\) points (and correspondingly other function families). Thus, our amortized per bit runtime would be just slightly increased. Furthermore, note that adjusting the IND-CPA-D security level would also affect the runtime in all prior works as well, which will thus maintain our advantage, if not further increase.
- 24.
Since \(f_2\) is only degree 1, the scalar multiplication can be saved by changing the \(\textsf{SlotToCoeff}\) matrix U to be multiplied with this scalar first. See detailed description in our full version [51] paragraph “Combining \(\textsf{SlotToCoeff}\) and \(f_\textsf{pre}\)”.
- 25.
In Table 2, we use ciphertext modulus of 650 bits instead of 860 bits. Using 860, which is essentially the maximum for 128-bit security, our bootstrapping takes about 91 s using GCP e2-standard-4.
- 26.
Note that a more recent version of this paper uses a larger database size. However, the analysis and our advantages remain exactly the same.
References
Lattigo v2.1.1. Online (December 2020). ePFL-LDS. http://github.com/ldsec/lattigo
Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Crypt. 9(3), 169–203 (2015)
Alperin-Sheriff, J., Peikert, C.: Practical bootstrapping in quasilinear time. In: Canetti, R., Garay, J.A. (eds.) Advances in Cryptology – CRYPTO 2013. pp. 1–20. Springer Berlin Heidelberg, Berlin, Heidelberg (2013)
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
Bossuat, J.P., Mouchet, C., Troncoso-Pastoriza, J., Hubaux, J.P.: Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys. In: Canteaut, A., Standaert, F.X. (eds.) Advances in Cryptology – EUROCRYPT 2021. pp. 587–617. Springer International Publishing, Cham (2021)
Brakerski, Z.: Fully homomorphic encryption without modulus switching from classical gapsvp. In: Proceedings of the 32nd Annual Cryptology Conference on Advances in Cryptology — CRYPTO 2012 - Volume 7417, p. 868–886. Springer-Verlag (2012)
Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (leveled) fully homomorphic encryption without bootstrapping. ACM Trans. Comput. Theor. (TOCT) 6(3), 1–36 (2014)
Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. In: Ostrovsky, R. (ed.) 52nd FOCS, October 22–25, 2011, pp. 97–106. IEEE Computer Society Press (2011)
Brakerski, Z., Vaikuntanathan, V.: Fully homomorphic encryption from ring-LWE and security for key dependent messages. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 505–524. Springer, Heidelberg, Germany (Aug 14–18, 2011)
Camenisch, J., Dubovitskaya, M., Neven, G.: Oblivious transfer with access control. In: Al-Shaer, E., Jha, S., Keromytis, A.D. (eds.) ACM CCS 2009, November 9–13, 2009, pp. 131–140. ACM Press (2009)
Casacuberta, S., Hesse, J., Lehmann, A.: SoK: oblivious pseudorandom functions. IEEE EuroS &P 2022 (2022). https://eprint.iacr.org/2022/302
Chakraborti, A., Reiter, M.K., Fanti, G.C.: This paper is included in the proceedings of the 32nd USENIX security symposium. In: USENIX 2023 (2023). https://api.semanticscholar.org/CorpusID:245537395
Chen, H., Chillotti, I., Song, Y.: Improved bootstrapping for approximate homomorphic encryption. In: Ishai, Y., Rijmen, V. (eds.) Advances in Cryptology – EUROCRYPT 2019. pp. 34–54. Springer International Publishing, Cham (2019)
Chen, H., Han, K.: Homomorphic lower digits removal and improved FHE bootstrapping. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018, Part I. LNCS, vol. 10820, pp. 315–337. Springer, Heidelberg, Germany (Apr 29 – May 3, 2018)
Cheon, J.H., Choe, H., Passelègue, A., Stehlé, D., Suvanto, E.: Attacks against the INDCPA-D security of exact FHE schemes. In: CCS (2024)
Cheon, J.H., Han, K., Kim, A., Kim, M., Song, Y.: Bootstrapping for approximate homomorphic encryption. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 360–384. Springer (2018)
Cheon, J.H., Kim, A., Kim, M., Song, Y.: Homomorphic encryption for arithmetic of approximate numbers. In: International Conference on the Theory and Application of Cryptology and Information Security. pp. 409–437. Springer (2017)
Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. In: Cheon, J.H., Takagi, T. (eds.) Advances in Cryptology – ASIACRYPT 2016. pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_1
Chor, B., Goldreich, O., Kushilevitz, E., Sudan, M.: Private information retrieval. In: 36th FOCS, pp. 41–50. IEEE Computer Society Press (1995)
Dalvi, A., Jain, A., Moradiya, S., Nirmal, R., Sanghavi, J., Siddavatam, I.: Securing neural networks using homomorphic encryption. In: 2021 International Conference on Intelligent Technologies (CONIT), pp. 1–7 (2021). https://doi.org/10.1109/CONIT51480.2021.9498376
Ducas, L., Micciancio, D.: FHEW: Bootstrapping Homomorphic Encryption in Less Than a Second. In: Oswald, E., Fischlin, M. (eds.) Advances in Cryptology – EUROCRYPT 2015. pp. 617–640. Springer, Berlin, Heidelberg (2015)
Fan, J., Vercauteren, F.: Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144 (2012). https://ia.cr/2012/144
Fisch, B., Lazzaretti, A., Liu, Z., Papamanthou, C.: ThorPIR: single server PIR via homomorphic thorp shuffles. In: CCS 2024 (2024)
Freedman, M.J., Nissim, K., Pinkas, B.: Efficient private matching and set intersection. In: Cachin, C., Camenisch, J. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 1–19. Springer, Heidelberg, Germany (May 2–6, 2004)
Geelen, R., Iliashenko, I., Kang, J., Vercauteren, F.: On polynomial functions modulo \(p^e\) and faster bootstrapping for homomorphic encryption. In: Eurocrypt 2023 (2023). https://eprint.iacr.org/2022/1364
Geelen, R., Vercauteren, F.: Bootstrapping for BGV and BFV revisited. J. Cryptol. 36(2) (2023)
Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing, pp. 169–178 (2009)
Gentry, C., Sahai, A., Waters, B.: Homomorphic encryption from learning with errors: conceptually-simpler, asymptotically-faster, attribute-based. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 75–92, Aug. 18–22, 2013. Springer, Heidelberg (2013)
Guimarães, A., Pereira, H.V.L., van Leeuwen, B.: Amortized bootstrapping revisited: simpler, asymptotically-faster, implemented. In: Asiacrypt 2023 (2023). https://eprint.iacr.org/2023/014
Halevi, S., Shoup, V.: HElib (2014). https://github.com/homenc/HElib
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
Halevi, S., Shoup, V.: Bootstrapping for HElib. J. Crypt. 34(1), 7 (2021)
Han, K., Hhan, M., Cheon, J.H.: Improved homomorphic discrete Fourier transforms and FHE bootstrapping. IEEE Access 7, 57361–57370 (2019). https://doi.org/10.1109/ACCESS.2019.2913850
Han, K., Ki, D.: Better bootstrapping for approximate homomorphic encryption. In: Cryptographers’ Track at the RSA Conference. pp. 364–390. Springer (2020)
HU, J., Chen, J., Dai, W., Wang, H.: Fully homomorphic encryption-based protocols for enhanced private set intersection functionalities. Cryptology ePrint Archive, Paper 2023/1407 (2023). https://eprint.iacr.org/2023/1407
Juvekar, C., Vaikuntanathan, V., Chandrakasan, A.: GAZELLE: a low latency framework for secure neural network inference. In: Enck, W., Felt, A.P. (eds.) USENIX Security 2018, pp. 1651–1669. USENIX Association (2018)
Kim, A., Polyakov, Y., Zucca, V.: Revisiting homomorphic encryption schemes for finite fields. In: ASIACRYPT 2021. p. 608–639. Springer (2021)
Kim, J., Seo, J., Song, Y.: Simpler and faster BFV bootstrapping for arbitrary plaintext modulus from CKKS. Cryptology ePrint Archive, Paper 2024/109 (2024). https://eprint.iacr.org/2024/109
Kim, S., Park, M., Kim, J., Kim, T., Min, C.: Evalround algorithm in CKKS bootstrapping. In: Asiacrypt 2022 (2022). https://eprint.iacr.org/2022/1256
Lee, D., Min, S., Song, Y.: Functional bootstrapping for FV-style cryptosystems. Cryptology ePrint Archive, Paper 2024/181 (2024). https://eprint.iacr.org/2024/181
Lee, J.W., et al.: Privacy-preserving machine learning with fully homomorphic encryption for deep neural network. IEEE Access 10, 30039–30054 (2022). https://doi.org/10.1109/ACCESS.2022.3159694
Lee, J.W., Lee, E., Kim, Y.S., No, J.S.: Rotation key reduction for client-server systems of deep neural network on fully homomorphic encryption. In: Guo, J., Steinfeld, R. (eds.) Advances in Cryptology, ASIACRYPT 2023, pp. 36–68. Springer, Singapore (2023). https://doi.org/10.1007/978-981-99-8736-8_2
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: EUROCRYPT 2021, pp. 618–647 (2021)
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 8, 144321–144330 (2020). https://doi.org/10.1109/ACCESS.2020.3014369
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–256. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-30620-4_8
Li, B., Micciancio, D.: On the security of homomorphic encryption on approximate numbers. In: EUROCRYPT 2021 (2021)
Lin, C., Liu, Z., Malkin, T.: XSPIR: efficient symmetrically private information retrieval from ring-LWE. In: Atluri, V., Di Pietro, R., Jensen, C.D., Meng, W. (eds.) ESORICS 2022, Part I. LNCS, vol. 13554, pp. 217–236. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-17140-6_11
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–352. Springer Nature Switzerland, Cham (2023)
Liu, F.H., Wang, H.: Batch bootstrapping i: bootstrapping in polynomial modulus only requires o (1) FHE multiplications in amortization. In: Hazay, C., Stam, M. (eds.) Advances in Cryptology – EUROCRYPT 2023, pp. 321–352. Springer, Cham (2023)
Liu, Z., Wang, Y.: Amortized functional bootstrapping in less than 7ms, with \(\tilde{O}(1)\) polynomial multiplications. In: Asiacrypt 2023 (2023). https://eprint.iacr.org/2023/910
Liu, Z., Wang, Y.: Relaxed functional bootstrapping: a new perspective on BGV/BFV bootstrapping. Cryptology ePrint Archive, Paper 2024/172 (2024)
jie Lu, W., Huang, Z., Hong, C., Ma, Y., Qu, H.: PEGASUS: bridging polynomial and non-polynomial evaluations in homomorphic encryption. In: 2021 IEEE Symposium on Security and Privacy, pp. 1057–1073. IEEE Computer Society Press (2021)
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 (2024). https://eprint.iacr.org/2024/115
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)
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
Okada, H., Player, R., Pohmann, S.: Homomorphic polynomial evaluation using Galois structure and applications to BFV bootstrapping. In: Asiacrypt 2023 (2023). https://eprint.iacr.org/2023/1304
Microsoft SEAL (2020). https://github.com/Microsoft/SEAL
Uzun, E., Chung, S.P., Kolesnikov, V., Boldyreva, A., Lee, W.: Fuzzy labeled private set intersection with applications to private real-time biometric search. In: Bailey, M., Greenstadt, R. (eds.) USENIX Security 2021, pp. 911–928. USENIX Association (2021)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2025 International Association for Cryptologic Research
About this paper
Cite this paper
Liu, Z., Wang, Y. (2025). Relaxed Functional Bootstrapping: A New Perspective on BGV/BFV Bootstrapping. In: Chung, KM., Sasaki, Y. (eds) Advances in Cryptology – ASIACRYPT 2024. ASIACRYPT 2024. Lecture Notes in Computer Science, vol 15484. Springer, Singapore. https://doi.org/10.1007/978-981-96-0875-1_7
Download citation
DOI: https://doi.org/10.1007/978-981-96-0875-1_7
Published:
Publisher Name: Springer, Singapore
Print ISBN: 978-981-96-0874-4
Online ISBN: 978-981-96-0875-1
eBook Packages: Computer ScienceComputer Science (R0)