Optimisations and Tradeoffs for HElib | SpringerLink
Skip to main content
Springer Nature Link
Log in

Optimisations and Tradeoffs for HElib

  • Conference paper
  • First Online:
Topics in Cryptology – CT-RSA 2023 (CT-RSA 2023)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13871))

Included in the following conference series:

Abstract

In this work, we investigate the BGV scheme as implemented in HElib. We begin by performing an implementation-specific noise analysis of BGV. This allows us to derive much tighter bounds than what was previously done. To confirm this, we compare our bounds against the state of the art. We find that, while our bounds are at most 1.8 bits off the experimentally observed values, they are as much as 29 bits tighter than previous work. Finally, to illustrate the importance of our results, we propose new and optimised parameters for HElib. In HElib, the special modulus is chosen to be k times larger than the current ciphertext modulus \(Q_i\). For a ratio of subsequent ciphertext moduli \(\log (\frac{Q_i}{Q_{i-1}}) = 54\) (a very common choice in HElib), we can optimise k by up to 26 bits. This means that we can either enable more multiplications without having to switch to larger parameters, or reduce the size of the evaluation keys, thus reducing on communication costs in relevant applications. We argue that our results are near-optimal.

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

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Akavia, A., Feldman, D., Shaul, H.: Secure search on encrypted data via multi-ring sketch. In: Lie, D., Mannan, M., Backes, M., Wang, X.F. (eds.) ACM CCS 2018, pp. 985–1001. ACM Press (2018)

    Google Scholar 

  2. Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)

    Article  MathSciNet  MATH  Google Scholar 

  3. 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–886. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_50

    Chapter  Google Scholar 

  4. Brakerski, Z., Gentry, C., Vaikuntanathan, V.: (Leveled) fully homomorphic encryption without bootstrapping. In: Goldwasser, S. (ed.) ITCS 2012, pp. 309–325. ACM (2012)

    Google Scholar 

  5. 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–437. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70694-8_15

    Chapter  Google Scholar 

  6. 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.) ASIACRYPT 2016. LNCS, vol. 10031, pp. 3–33. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53887-6_1

    Chapter  MATH  Google Scholar 

  7. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: Faster packed homomorphic operations and efficient circuit bootstrapping for TFHE. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. Part I, volume 10624 of LNCS, pp. 377–408. Springer, Heidelberg (2017)

    Chapter  Google Scholar 

  8. Chillotti, I., Gama, N., Georgieva, M., Izabachène, M.: TFHE: fast fully homomorphic encryption over the torus. J. Cryptol. 33(1), 34–91 (2020)

    Article  MathSciNet  MATH  Google Scholar 

  9. Chillotti, I., Ligier, D., Orfila, J.-B., Tap, S.: Improved programmable bootstrapping with larger precision and efficient arithmetic circuits for TFHE. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13092, pp. 670–699. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92078-4_23

    Chapter  Google Scholar 

  10. Cid, C., Indrøy, J.P., Raddum, H.: FASTA – a stream cipher for fast FHE evaluation. In: Galbraith, S.D. (ed.) CT-RSA 2022. LNCS, vol. 13161, pp. 451–483. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-95312-6_19

    Chapter  Google Scholar 

  11. Costache, A., Smart, N.P.: Which ring based somewhat homomorphic encryption scheme is best? In: Sako, K. (ed.) CT-RSA 2016. LNCS, vol. 9610, pp. 325–340. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-29485-8_19

    Chapter  Google Scholar 

  12. Costache, A., Curtis, B.R., Hales, E., Murphy, S., Ogilvie, T., Player, R.: On the precision loss in approximate homomorphic encryption. Cryptology ePrint Archive, Paper 2022/162 (2022). https://eprint.iacr.org/2022/162

  13. Costache, A., Laine, K., Player, R.: Evaluating the effectiveness of heuristic worst-case noise analysis in FHE. In: Chen, L., Li, N., Liang, K., Schneider, S. (eds.) ESORICS 2020. LNCS, vol. 12309, pp. 546–565. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-59013-0_27

    Chapter  Google Scholar 

  14. Costache, A., Nürnberger, L., Player, R.: Optimisations and trade-offs for HElib. Cryptology ePrint Archive, Paper 2023/104 (2023). https://eprint.iacr.org/2023/104

  15. Crawford, J.L.H., Gentry, C., Halevi, S., Platt, D., Shoup, V.: Doing real work with FHE: the case of logistic regression. In: Brenner, M., Rohloff, K. (eds.) Proceedings of the 6th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, WAHC@CCS 2018, Toronto, ON, Canada, 19 October 2018, pp. 1–12. ACM (2018)

    Google Scholar 

  16. Ducas, L., Micciancio, D.: Improved short lattice signatures in the standard model. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014. LNCS, vol. 8616, pp. 335–352. Springer, Heidelberg (2014). https://doi.org/10.1007/978-3-662-44371-2_19

    Chapter  MATH  Google Scholar 

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

  18. Gentry, C.: Fully homomorphic encryption using ideal lattices. In: Mitzenmacher, M. (ed.) 41st ACM STOC, pp. 169–178. ACM Press (2009)

    Google Scholar 

  19. Gentry, C., Halevi, S., Smart, N.P.: Fully homomorphic encryption with polylog overhead. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 465–482. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_28

    Chapter  Google Scholar 

  20. Gentry, C., Halevi, S., Smart, N.P.: Homomorphic evaluation of the AES circuit. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 850–867. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32009-5_49

    Chapter  Google Scholar 

  21. 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. LNCS, vol. 8042, pp. 75–92. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_5

    Chapter  Google Scholar 

  22. 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

  23. Halevi, S., Shoup, V.: Helib 2.2.1. GitHub Repository homenc/HElib (2021)

    Google Scholar 

  24. Iliashenko, I.: Optimisations of Fully Homomorphic Encryption. PhD thesis, KU Leuven (2019)

    Google Scholar 

  25. 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–639. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92078-4_21

    Chapter  Google Scholar 

  26. Kolmogorov, A.: Sulla determinazione empirica di una lgge di distribuzione. Inst. Ital. Attuari Giorn. 4, 83–91 (1933)

    Google Scholar 

  27. Lattigo v4. https://github.com/tuneinsight/lattigo. EPFL-LDS, Tune Insight SA (2022)

  28. Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: Bugliesi, M., Preneel, B., Sassone, V., Wegener, I. (eds.) ICALP 2006. LNCS, vol. 4052, pp. 144–155. Springer, Heidelberg (2006). https://doi.org/10.1007/11787006_13

    Chapter  Google Scholar 

  29. Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_1

    Chapter  Google Scholar 

  30. Murphy, S., Player, R.: A central limit framework for ring-LWE decryption. Cryptology ePrint Archive, Report 2019/452 (2019). https://eprint.iacr.org/2019/452

  31. Palisade lattice cryptography library (release 1.10.6) (2020)

    Google Scholar 

  32. Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press (2005)

    Google Scholar 

  33. Microsoft SEAL (release 4.0). https://github.com/Microsoft/SEAL. Microsoft Research, Redmond, WA (2022)

  34. Smirnov, N.: Table for estimating the goodness of fit of empirical distributions. Ann. Math. Stat. 19(2), 279–281 (1948)

    Article  MathSciNet  MATH  Google Scholar 

Download references

Acknowledgements

We would like to thank Leroy Odunlami for insightful discussions on statistics and probability theory.

Author information

Authors and Affiliations

  1. Norwegian University of Science and Technology (NTNU), Trondheim, Norway

    Anamaria Costache & Lea Nürnberger

  2. Royal Holloway, University of London, London, UK

    Rachel Player

Authors
  1. Anamaria Costache
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Lea Nürnberger
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Rachel Player
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Lea Nürnberger .

Editor information

Editors and Affiliations

  1. Oregon State University, Corvallis, OR, USA

    Mike Rosulek

Rights and permissions

Reprints and permissions

Copyright information

© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Costache, A., Nürnberger, L., Player, R. (2023). Optimisations and Tradeoffs for HElib. In: Rosulek, M. (eds) Topics in Cryptology – CT-RSA 2023. CT-RSA 2023. Lecture Notes in Computer Science, vol 13871. Springer, Cham. https://doi.org/10.1007/978-3-031-30872-7_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-30872-7_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-30871-0

  • Online ISBN: 978-3-031-30872-7

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Search

Navigation