Communications in Cryptology IACR CiC

A Central Limit Approach for Ring-LWE Noise Analysis


Sean Murphy, Rachel Player
Sean Murphy
Royal Holloway, University of London, Egham, UK
s dot murphy at rhul dot ac dot uk
Rachel Player
Royal Holloway, University of London, Egham, UK
rachel dot player at rhul dot ac dot uk


This paper develops Central Limit arguments for analysing the noise in ciphertexts in two homomorphic encryption schemes that are based on Ring-LWE. The first main contribution of this paper is to present and evaluate an average-case noise analysis for the BGV scheme. Our approach relies on the recent work of Costache et al.(SAC 2023) that gives the approximation of a polynomial product as a multivariate Normal distribution. We show how this result can be applied in the BGV context and evaluate its efficacy. We find this average-case approach can much more closely model the noise growth in BGV implementations than prior approaches, but in some cases it can also underestimate the practical noise growth. Our second main contribution is to develop a Central Limit framework to analyse the noise growth in the homomorphic Ring-LWE cryptosystem of Lyubashevsky, Peikert and Regev (Eurocrypt 2013, full version). Our approach is very general: apart from finite variance, no assumption on the distribution of the noise is required (in particular, the noise need not be subgaussian). We show that our approach leads to tighter bounds for the probability of decryption failure than those of prior work.


Ahmad Al Badawi, Jack Bates, Flavio Bergamaschi, David Bruce Cousins, Saroja Erabelli, Nicholas Genise, Shai Halevi, Hamish Hunt, Andrey Kim, Yongwoo Lee, Zeyu Liu, Daniele Micciancio, Ian Quah, Yuriy Polyakov, Saraswathy R.V., Kurt Rohloff, Jonathan Saylor, Dmitriy Suponitsky, Matthew Triplett, Vinod Vaikuntanathan, and Vincent Zucca. OpenFHE: Open-Source Fully Homomorphic Encryption Library. In Proceedings of the 10th Workshop on Encrypted Computing & Applied Homomorphic Cryptography, pages 53-63, New York, NY, USA. 2022. Association for Computing Machinery. DOI: 10.1145/3560827.3563379
Andreea Alexandru, Ahmad Al Badawi, Daniele Micciancio, and Yuriy Polyakov. Application-Aware Approximate Homomorphic Encryption: Configuring FHE for Practical Use. Cryptology ePrint Archive, Paper 2024/203. 2024.
M. Albrecht, M. Chase, H. Chen, J. Ding, S. Goldwasser, S. Gorbunov, S. Halevi, J. Hoffstein, K. Laine, K. Lauter, S. Lokam, D. Micciancio, D. Moody, T. Morrison, A. Sahai, and V. Vaikuntanathan. Homomorphic Encryption Security Standard. Technical report, 2018.
Z. Brakerski, C. Gentry, and V. Vaikuntanathan. (Leveled) Fully Homomorphic Encryption without Bootstrapping. In Innovations in Theoretical Computer Science 2012, pages 309–325. 2012. ACM. DOI:
P. Billingsley. Probability and Measure. Wiley, Third edition. 1995.
Beatrice Biasioli and Chiara Marcolla. Personal communication.. 2023.
Beatrice Biasioli, Chiara Marcolla, Marco Calderini, and Johannes Mono. Improving and Automating BFV Parameters Selection: An Average-Case Approach. IACR Cryptol. ePrint Arch., 2023.
Anamaria Costache, Benjamin R. Curtis, Erin Hales, Sean Murphy, Tabitha Ogilvie, and Rachel Player. On the Precision Loss in Approximate Homomorphic Encryption. In Claude Carlet, Kalikinkar Mandal, and Vincent Rijmen, editors, Selected Areas in Cryptography - SAC 2023 - 30th International Conference, Fredericton, Canada, August 14-18, 2023, Revised Selected Papers, volume 14201 of Lecture Notes in Computer Science, pages 325–345. 2023. Springer. DOI: 10.1007/978-3-031-53368-6_16
Jung Hee Cheon, Hyeongmin Choe, Alain Passelègue, Damien Stehlé, and Elias Suvanto. Attacks Against the INDCPA-D Security of Exact FHE Schemes. Cryptology ePrint Archive, Paper 2024/127. 2024.
I. Chillotti, N. Gama, M. Georgieva, and M. Izabachène. Faster Fully Homomorphic Encryption: Bootstrapping in Less Than 0.1 Seconds. In J. H. Cheon and T. Takagi, editors, Advances in Cryptology - ASIACRYPT 2016, volume 10031 of LNCS, pages 3–33. 2016. Springer. DOI:
Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: Fast Fully Homomorphic Encryption Over the Torus. J. Cryptology, 33(1):34–91, 2020. DOI:
J. H. Cheon, A. Kim, M. Kim, and Y. S. Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In T. Takagi and T. Peyrin, editors, Advances in Cryptology - ASIACRYPT 2017, volume 10624 of LNCS, pages 409–437. 2017. Springer. DOI:
Anamaria Costache, Kim Laine, and Rachel Player. Evaluating the Effectiveness of Heuristic Worst-Case Noise Analysis in FHE. In Liqun Chen, Ninghui Li, Kaitai Liang, and Steve A. Schneider, editors, Computer Security - ESORICS 2020 - 25th European Symposium on Research in Computer Security, ESORICS 2020, Guildford, UK, September 14-18, 2020, Proceedings, Part II, volume 12309 of Lecture Notes in Computer Science, pages 546–565. 2020. Springer. DOI: 10.1007/978-3-030-59013-0_27
Anamaria Costache, Lea Nürnberger, and Rachel Player. Optimisations and Tradeoffs for HElib. In Mike Rosulek, editor, Topics in Cryptology - CT-RSA 2023 - Cryptographers' Track at the RSA Conference 2023, San Francisco, CA, USA, April 24-27, 2023, Proceedings, volume 13871 of Lecture Notes in Computer Science, pages 29–53. 2023. Springer. DOI:
Ana Costache and Nigel P. Smart. Which Ring Based Somewhat Homomorphic Encryption Scheme is Best?. In Kazue Sako, editor, Topics in Cryptology - CT-RSA 2016 - The Cryptographers' Track at the RSA Conference 2016, San Francisco, CA, USA, February 29 - March 4, 2016, Proceedings, volume 9610 of Lecture Notes in Computer Science, pages 325–340. 2016. Springer. DOI: 10.1007/978-3-319-29485-8_19
Marina Checri, Renaud Sirdey, Aymen Boudguiga, and Jean-Paul Bultel. On the practical CPAD security of “exact” and threshold FHE schemes and libraries. Cryptology ePrint Archive, Paper 2024/116. 2024.
J. Fan and F. Vercauteren. Somewhat Practical Fully Homomorphic Encryption. IACR Cryptology ePrint Archive, 2012:144, 2012.
C. Gentry. Fully Homomorphic Encryption using Ideal Lattices. In M. Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, pages 169–178. 2009. DOI:
Craig Gentry, Shai Halevi, and Nigel P. Smart. Fully Homomorphic Encryption with Polylog Overhead. In David Pointcheval and Thomas Johansson, editors, Advances in Cryptology - EUROCRYPT 2012 - 31st Annual International Conference on the Theory and Applications of Cryptographic Techniques, Cambridge, UK, April 15-19, 2012. Proceedings, volume 7237 of Lecture Notes in Computer Science, pages 465–482. 2012. Springer. DOI: 10.1007/978-3-642-29011-4_28
Craig Gentry, Shai Halevi, and Nigel P. Smart. Homomorphic Evaluation of the AES Circuit. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology - CRYPTO 2012 - 32nd Annual Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012. Proceedings, volume 7417 of Lecture Notes in Computer Science, pages 850–867. 2012. Springer. DOI: 10.1007/978-3-642-32009-5_49
Qian Guo, Denis Nabokov, Elias Suvanto, and Thomas Johansson. Key Recovery Attacks on Approximate Homomorphic Encryption with Non-Worst-Case Noise Flooding Countermeasures. In 33rd USENIX Security Symposium (USENIX Security 24). Philadelphia, PA: USENIX Association. 2024. Pre-proceedings version available at
G. Grimmett and D. Stirzaker. Probability And Random Processes. Oxford University Press, 3rd edition. 2001.
C. Gentry, A. Sahai, and B. Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In R. Canetti and J.A. Garay, editors, Advances in Cryptology - CRYPTO 2013, volume 8042 of LNCS, pages 75–92. 2013. Springer. DOI:
HElib. January 2019.
Shai Halevi and Victor Shoup. Design and implementation of HElib: a homomorphic encryption library. Cryptology ePrint Archive, Paper 2020/1481. 2020.
I. Iliashenko. Optimisations of fully homomorphic encryption. PhD thesis, KU Leuven, 2019.
Andrey Kim, Antonis Papadimitriou, and Yuriy Polyakov. Approximate Homomorphic Encryption with Reduced Approximation Error. In Steven D. Galbraith, editor, Topics in Cryptology - CT-RSA 2022 - Cryptographers' Track at the RSA Conference 2022, Virtual Event, March 1-2, 2022, Proceedings, volume 13161 of Lecture Notes in Computer Science, pages 120–144. 2022. Springer. DOI: 10.1007/978-3-030-95312-6_6
Andrey Kim, Yuriy Polyakov, and Vincent Zucca. Revisiting Homomorphic Encryption Schemes for Finite Fields. In Mehdi Tibouchi and Huaxiong Wang, editors, Advances in Cryptology - ASIACRYPT 2021 - 27th International Conference on the Theory and Application of Cryptology and Information Security, Singapore, December 6-10, 2021, Proceedings, Part III, volume 13092 of Lecture Notes in Computer Science, pages 608–639. 2021. Springer. DOI: 10.1007/978-3-030-92078-4_21
B. Li, D. Micciancio, M. Schutz, and J. Sorrel. Securing Approximate Homomorphic Encryption using Differential Privacy. In Y. Dodis and T. Shrimpton, editors, Advances in Cryptology - CRYPTO 2022, volume LNCS 13507, pages 560-589. 2022. DOI:
V. Lyubashevsky, C. Peikert, and O. Regev. On Ideal Lattices and Learning with Errors Over Rings. IACR Cryptology ePrint Archive, 2012:230, 2012.
V. Lyubashevsky, C. Peikert, and O. Regev. A Toolkit for Ring-LWE Cryptography. IACR Cryptology ePrint Archive, 2013:293, 2013.
V. Lyubashevsky, C. Peikert, and O. Regev. A Toolkit for Ring-LWE Cryptography. In T. Johansson and P. Nguyen, editors, Advances in Cryptology - EUROCRYPT 2013, volume 7881 of LNCS, pages 35–54. 2013. Springer.
D. Micciancio and C. Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In D. Pointcheval and T. Johansson, editors, Eurocrypt 2012, volume 7237 of LNCS, pages 700-718. 2012. Springer. DOI:
S. Murphy and R. Player. $\delta$-subgaussian Random Variables in Cryptography. In J. Jang-Jaccard and F. Guo, editors, ACISP 2019: The 24th Australasian Conference on Information Security and Privacy, volume 11547 of LNCS, pages 251-268. 2019. Springer. DOI:
Sean Murphy and Rachel Player. Discretisation and Product Distributions in Ring-LWE. Journal of Mathematical Cryptology, 15:45–59, 2020. DOI:
D. Micciancio and O. Regev. Lattice-based Cryptography. In D.J. Bernstein, J. Buchmann, and E. Dahmen, editors, Post-Quantum Cryptography, pages 147-191. 2009. Springer. DOI: 10.1007/978-3-540-88702-7_5
Chris Peikert. A Decade of Lattice Cryptography. Foundations and Trends in Theoretical Computer Science, 10(4):283–424, 2016. DOI:
Rachel Player. Parameter selection in lattice-based cryptography. PhD thesis, Royal Holloway, University of London, 2018.
O. Regev. On Lattices, Learning with Errors, Random Linear Codes and Cryptography. In H. Gabow and R. Fagin, editors, 37th Annual ACM Symposium of Theory of Computing. 2005. DOI:
O. Regev. The Learning with Errors Problem (Invited Survey). In IEEE Conference on Computational Complexity, pages 191-204. 2010. DOI:
Microsoft SEAL (release 4.0). Microsoft Research, Redmond, WA.. March 2022.
D. Stehlé, R. Steinfeld, K. Tanaka, and K. Xagawa. Efficient Public Key Encryption Based on Ideal Lattices. In M. Matsui, editor, Advances in Cryptology - ASIACRYPT 2009, volume 5912 of LNCS, pages 617–635. 2009. DOI:
D. Stroock. Probability Theory: An Analytic View. Cambridge University Press 2011.
T. Tao and Van Vu. Random matrices: Universality of local eigenvalue statistics. Acta Mathematica, 206:127-204, 2011. DOI:

PDFPDF Open access

Submitted: 2024-03-20
Accepted: 2024-06-03
Published: 2024-07-08
How to cite

Sean Murphy and Rachel Player, "A Central Limit Approach for Ring-LWE Noise Analysis," IACR Communications in Cryptology, vol. 1, no. 2, Jul 08, 2024, doi: 10.62056/ay76c0kr.


Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.