Skip to main content
SpringerLink
Log in

Bootstrapping for BGV and BFV Revisited

  • Research Article
  • Published:
Journal of Cryptology Aims and scope Submit manuscript

Abstract

We unify the state-of-the-art bootstrapping algorithms for BGV and BFV in a single framework and show that both schemes can be bootstrapped with identical complexity. This result corrects a claim by Chen and Han (Eurocrypt 2018) that BFV is more efficient to bootstrap than BGV. We also fix an error in their optimized procedure for power-of-two cyclotomics, which occurs for some parameter sets. Our analysis is simpler, yet more general than earlier work, in that it simultaneously covers both BGV and BFV. Furthermore, we also design and implement a high-level open source software library for bootstrapping in the Magma Computer Algebra System. It is the first library to support both BGV and BFV bootstrapping in full generality, with all recent techniques (including the above fixes) and trade-offs.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

Notes

  1. See https://github.com/homenc/HElib for bootstrapping in HElib

  2. This implementation was never publicly released.

  3. Available at https://github.com/KULeuven-COSIC/Bootstrapping_BGV_BFV.

  4. In their most general version, BGV and BFV support any positive integer as plaintext modulus. However, bootstrapping is restricted to prime powers only.

  5. This requirement can be relaxed to \(\gcd (q, p)=1\) if we multiply the second part of Eq. (8) by \(q^{-1}\) and the third part by q, where \(q^{-1}\cdot q = 1 (\textrm{mod}\ p^e)\). However, we only treat \(q = 1 (\textrm{mod}\ p^e)\) so that Eq. (8) is nearly identical for BFV.

  6. In fact, the analysis only holds if the linear transformations from Sect. 4 exploit the prime-power factorization of m.

  7. The non-cyclic case could be handled by multi-dimensional linear transformations. However, if we exploit the prime-power factorization of m, then this situation can only occur if m is divisible by 8 [7].

  8. Alleviating this restriction would result in intermediate F-linear transformations, where \(\mathbb {Z}_{p^r} \subseteq F \subseteq E\). All stages of the evaluation map (explained later) can be treated as a special case of this situation.

  9. Recall that the inverse evaluation map is computed with respect to a higher precision plaintext space modulo \(p^e\) with \(e > r\). Therefore the constants \(c_f\) come from \(\mathbb {Z}_{p^e}\).

  10. If \(p = 2\), we consider the digits in \(\{0, 1\}\). Hence the output of digit extraction changes to \(\lfloor {w/p^v} \rfloor \). However, bootstrapping requires a rounding operation instead of flooring. Fortunately, this can be fixed by applying the simple equality \(\lfloor {x} \rceil = \lfloor {x+1/2} \rfloor \).

  11. Recall that only the first hypercube dimension can be bad. The cost for stages \(2, \ldots , t\) is therefore only relevant in good hypercube dimensions.

References

  1. J. Alperin-Sheriff, C. Peikert, Practical bootstrapping in quasilinear time, in Annual Cryptology Conference (Springer, 2013), pp. 1–20

  2. A.A. Badawi, J. Bates, F. Bergamaschi, D.B. Cousins, S. Erabelli, N. Genise, S. Halevi, H. Hunt, A. Kim, Y. Lee, Z. Liu, D. Micciancio, I. Quah, Y. Polyakov, S. R.V., K. Rohloff, J. Saylor, D. Suponitsky, M. Triplett, V. Vaikuntanathan, V. Zucca, Openfhe: Open-source fully homomorphic encryption library. Cryptology ePrint Archive, Paper 2022/915, 2022. https://eprint.iacr.org/2022/915.

  3. J.-P. Bossuat, C. Mouchet, J. Troncoso-Pastoriza, J.-P. Hubaux, Efficient bootstrapping for approximate homomorphic encryption with non-sparse keys, in A. Canteaut, F.-X. Standaert, editors, Advances in Cryptology – EUROCRYPT 2021 (Springer, Cham, 2021), pp. 587–617

  4. J.-P. Bossuat, J.R. Troncoso-Pastoriza, J.-P. Hubaux, Bootstrapping for approximate homomorphic encryption with negligible failure-probability by using sparse-secret encapsulation. Cryptology ePrint Archive, Paper 2022/024 (2022). https://eprint.iacr.org/2022/024.

  5. C. Boura, N. Gama, M. Georgieva, D. Jetchev, Simulating homomorphic evaluation of deep learning predictions, in International Symposium on Cyber Security Cryptography and Machine Learning (Springer, 2019), pp. 212–230

  6. Z. Brakerski, C. Gentry, V. Vaikuntanathan, (Leveled) fully homomorphic encryption without bootstrapping, in Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ITCS ’12 (ACM, 2012), pp. 309–325

  7. R. Burn, Disquisitiones arithmeticae (2nd printing), by cf gauss, trans by aa clarke. pp 490. dm 148. 1986. isbn 3-540-96254-9 (springer). Math. Gazette 71(457), 249–249 (1987)

  8. H. Chen, K. Han, Homomorphic lower digits removal and improved the bootstrapping, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2018), pp. 315–337

  9. H. Chen, Z. Huang, K. Laine, P. Rindal, Labeled psi from fully homomorphic encryption with malicious security, in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security (2018), pp. 1223–1237

  10. J. H. Cheon, A. Kim, M. Kim, Y. Song, Homomorphic encryption for arithmetic of approximate numbers. Cryptology ePrint Archive, Paper 2016/421 (2016). https://eprint.iacr.org/2016/421

  11. I. Chillotti, N. Gama, M. Georgieva, M. Izabachène, Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds. Cryptology ePrint Archive, Paper 2016/870 (2016). https://eprint.iacr.org/2016/870

  12. R. Cramer, R. Gennaro, B. Schoenmakers, A secure and optimally efficient multi-authority election scheme. Eur. Trans. Telecommun. 8(5), 481–490 (1997)

    Article  Google Scholar 

  13. S. Devadas, M. van Dijk, C.W. Fletcher, L. Ren, E. Shi, D. Wichs, Onion oram: A constant bandwidth blowup oblivious ram, in Theory of Cryptography Conference (Springer, 2016), pp. 145–174

  14. C. Dong, L. Chen, A fast single server private information retrieval protocol with low communication cost, in Computer Security - ESORICS 2014, volume 8712 of Lecture Notes in Computer Science (Springer, Cham, 2014), pp. 380–399

  15. L. Ducas, D. Micciancio, Fhew: Bootstrapping homomorphic encryption in less than a second. Cryptology ePrint Archive, Paper 2014/816 (2014). https://eprint.iacr.org/2014/816

  16. J. Fan, F. Vercauteren, Somewhat practical fully homomorphic encryption. Cryptology ePrint Archive, Report 2012/144 (2012). https://eprint.iacr.org/2012/144

  17. R. Geelen, I. Iliashenko, J. Kang, F. Vercauteren, On polynomial functions modulo \(p^e\) and faster bootstrapping for homomorphic encryption. Cryptology ePrint Archive, Paper 2022/1364 (2022). https://eprint.iacr.org/2022/1364

  18. R. Geelen, M. Van Beirendonck, H.V. Pereira, B. Huffman, T. McAuley, B. Selfridge, D. Wagner, G. Dimou, I. Verbauwhede, F. Vercauteren, et al, Basalisc: Flexible asynchronous hardware accelerator for fully homomorphic encryption (2022). arXiv:2205.14017

  19. C. Gentry, Fully homomorphic encryption using ideal lattices, in Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing (2009), pp. 169–178

  20. C. Gentry, S. Halevi, Implementing gentry’s fully-homomorphic encryption scheme, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2011), pp. 129–148

  21. C. Gentry, S. Halevi, N.P. Smart, Better bootstrapping in fully homomorphic encryption, in International Workshop on Public Key Cryptography (Springer, 2012), pp. 1–16

  22. C. Gentry, S. Halevi, N.P. Smart, Fully homomorphic encryption with polylog overhead, in Advances in Cryptology – EUROCRYPT 2012, volume 7237 of Lecture Notes in Computer Science (Springer, Berlin, Heidelberg, 2012), pp. 465–482

  23. C. Gentry, S. Halevi, N.P. Smart, Homomorphic evaluation of the AES circuit, in Annual Cryptology Conference (Springer, 2012), pp. 850–867

  24. C. Gentry, A. Sahai, B. Waters, Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Cryptology ePrint Archive, Paper 2013/340 (2013). https://eprint.iacr.org/2013/340

  25. S. Halevi, V. Shoup, Algorithms in helib. Cryptology ePrint Archive, Report 2014/106 (2014). https://eprint.iacr.org/2014/106

  26. S. Halevi, V. Shoup, Bootstrapping for helib, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2015), pp. 641–670

  27. S. Halevi, V. Shoup, Faster homomorphic linear transformations in helib, in Annual International Cryptology Conference (Springer, 2018), pp. 93–120

  28. S. Halevi, V. Shoup, Design and implementation of helib: a homomorphic encryption library. Cryptology ePrint Archive, Report 2020/1481 (2020). https://eprint.iacr.org/2020/1481

  29. S. Halevi, V. Shoup, Bootstrapping for helib. J. Cryptol. 34(1), 1–44 (2021)

    Article  MathSciNet  MATH  Google Scholar 

  30. C.S. Jutla, N. Manohar, Sine series approximation of the mod function for bootstrapping of approximate he. Cryptology ePrint Archive, Paper 2021/572 (2021). https://eprint.iacr.org/2021/572

  31. A. Kim, M. Deryabin, J. Eom, R. Choi, Y. Lee, W. Ghang, D. Yoo, General bootstrapping approach for rlwe-based homomorphic encryption. Cryptology ePrint Archive, Paper 2021/691 (2021). https://eprint.iacr.org/2021/691

  32. A. Kim, Y. Polyakov, V. Zucca, Revisiting homomorphic encryption schemes for finite fields, in International Conference on the Theory and Application of Cryptology and Information Security (Springer, 2021), pp. 608–639

  33. J.-W. Lee, E. Lee, Y. Lee, Y.-S. Kim, J.-S. No, High-precision bootstrapping of rns-ckks homomorphic encryption using optimal minimax polynomial approximation and inverse sine function, in A. Canteaut, F.-X. Standaert, editors, Advances in Cryptology – EUROCRYPT 2021 (Springer, Cham, 2021), pp. 618–647

  34. Y. Lee, J.-W. Lee, Y.-S. Kim, Y. Kim, J.-S. No, H. Kang, High-precision bootstrapping for approximate homomorphic encryption by error variance minimization, in O. Dunkelman, S. Dziembowski, editors, Advances in Cryptology – EUROCRYPT 2022 (Springer, Cham, 2022), pp. 551–580

  35. R. Li, C. Jia, Homomorphic modular reduction and improved bootstrapping for bgv scheme, in Information Security and Cryptology, volume 13007 of Lecture Notes in Computer Science (Springer, Cham, 2021), pp. 466–484

  36. V. Lyubashevsky, C. Peikert, O. Regev, A toolkit for ring-lwe cryptography, in Annual International Conference on the Theory and Applications of Cryptographic Techniques (Springer, 2013), pp. 35–54

  37. M.S. Paterson, L.J. Stockmeyer, On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2(1), 60–66 (1973)

    Article  MathSciNet  MATH  Google Scholar 

  38. R.L. Rivest, L. Adleman, M.L. Dertouzos, et al, On data banks and privacy homomorphisms. Found. Secure Comput. 4(11), 169–180 (1978)

    MathSciNet  Google Scholar 

  39. S. Roman, Field Theory, vol. 158 (Springer, 2005)

    Google Scholar 

  40. T. Rondeau, Data protection in virtual environments (DPRIVE) (2020)

  41. N.P. Smart, F. Vercauteren, Fully homomorphic simd operations. Des. Codes Cryptogr. 71(1), 57–81 (2014)

    Article  MATH  Google Scholar 

  42. V. Zucca, Towards efficient arithmetic for ring-lwe based homomorphic encryption (2018)

Download references

Acknowledgements

This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. HR0011-21-C-0034. The views, opinions, and/or findings expressed are those of the authors and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government. This work was additionally supported in part by CyberSecurity Research Flanders with reference number VR20192203. Robin Geelen is funded in part by Research Foundation - Flanders (FWO) under a Ph.D. Fellowship fundamental research (Project Number 1162123N).

Author information

Authors and Affiliations

  1. imec-COSIC, ESAT, KU Leuven, Leuven, Belgium

    Robin Geelen & Frederik Vercauteren

Authors
  1. Robin Geelen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Frederik Vercauteren
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Robin Geelen.

Additional information

Communicated by David Pointcheval and Nigel Smart.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

This paper was reviewed by Kyoohyung Han and Yuriy Polyakov

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Geelen, R., Vercauteren, F. Bootstrapping for BGV and BFV Revisited. J Cryptol 36, 12 (2023). https://doi.org/10.1007/s00145-023-09454-6

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s00145-023-09454-6

Keywords

Search

Navigation