{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T17:59:54Z","timestamp":1767981594630,"version":"3.49.0"},"reference-count":48,"publisher":"International Association for Cryptologic Research","license":[{"start":{"date-parts":[[2024,3,20]],"date-time":"2024-03-20T00:00:00Z","timestamp":1710892800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IACR CiC"],"accepted":{"date-parts":[[2024,6,3]]},"abstract":"<jats:p>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. <\/jats:p>","DOI":"10.62056\/ay76c0kr","type":"journal-article","created":{"date-parts":[[2024,7,8]],"date-time":"2024-07-08T15:52:04Z","timestamp":1720453924000},"update-policy":"https:\/\/doi.org\/10.62056\/adfjwm02dj","source":"Crossref","is-referenced-by-count":6,"title":["A Central Limit Approach for Ring-LWE Noise Analysis"],"prefix":"10.62056","author":[{"given":"Sean","family":"Murphy","sequence":"first","affiliation":[{"name":"Royal Holloway, University of London","place":["Egham, UK"]}]},{"given":"Rachel","family":"Player","sequence":"additional","affiliation":[{"name":"Royal Holloway, University of London","place":["Egham, UK"]}]}],"member":"48349","published-online":{"date-parts":[[2024,7,8]]},"reference":[{"key":"ref1:STOC:Regev05","article-title":"On Lattices, Learning with Errors, Random Linear Codes and\n  Cryptography","volume-title":"37th Annual ACM Symposium of Theory of Computing","author":"O.\u00a0Regev","year":"2005"},{"key":"ref2:COCO:Regev10","first-page":"191","article-title":"The Learning with Errors Problem (Invited Survey)","volume-title":"IEEE Conference on Computational Complexity","author":"O.\u00a0Regev","year":"2010"},{"key":"ref3:PQCBook:MicReg09","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1007\/978-3-540-88702-7_5","article-title":"Lattice-based Cryptography","volume-title":"Post-Quantum Cryptography","author":"D.\u00a0Micciancio","year":"2009"},{"key":"ref4:peikert-lattice","doi-asserted-by":"crossref","first-page":"283","DOI":"10.1561\/0400000074","article-title":"A Decade of Lattice Cryptography","volume":"10","author":"Chris Peikert","year":"2016","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"ref5:AC:SSTX09","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"617","DOI":"10.1007\/978-3-642-10366-7_36","article-title":"Efficient Public Key Encryption Based on Ideal Lattices","volume-title":"Advances in Cryptology - ASIACRYPT 2009","volume":"5912","author":"D.\u00a0Stehl\u00e9","year":"2009"},{"key":"ref6:EC:LyuPeiReg10FULL","first-page":"230","article-title":"On Ideal Lattices and Learning with Errors Over Rings","volume":"2012","author":"V.\u00a0Lyubashevsky","year":"2012","journal-title":"IACR Cryptology ePrint Archive"},{"key":"ref7:STOC:Gentry09","series-title":"ACM","first-page":"169","article-title":"Fully Homomorphic Encryption using Ideal Lattices","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of\n  Computing, STOC 2009","author":"C.\u00a0Gentry","year":"2009"},{"key":"ref8:ITCS:BGV12","first-page":"309","article-title":"(Leveled) Fully Homomorphic Encryption without\n  Bootstrapping","volume-title":"Innovations in Theoretical Computer Science 2012","author":"Z.\u00a0Brakerski","year":"2012"},{"key":"ref9:FV12","first-page":"144","article-title":"Somewhat Practical Fully Homomorphic Encryption","volume":"2012","author":"J.\u00a0Fan","year":"2012","journal-title":"IACR Cryptology ePrint Archive"},{"key":"ref10:C:GSW13","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/978-3-642-40041-4_5","article-title":"Homomorphic Encryption from Learning with Errors:\n  Conceptually-Simpler, Asymptotically-Faster, Attribute-Based","volume-title":"Advances in Cryptology - CRYPTO 2013","volume":"8042","author":"C.\u00a0Gentry","year":"2013"},{"key":"ref11:toolkit","first-page":"293","article-title":"A Toolkit for Ring-LWE Cryptography","volume":"2013","author":"V.\u00a0Lyubashevsky","year":"2013","journal-title":"IACR Cryptology ePrint Archive"},{"key":"ref12:AC:CGGI16","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1007\/978-3-662-53887-6_1","article-title":"Faster Fully Homomorphic Encryption: Bootstrapping in Less\n  Than 0.1 Seconds","volume-title":"Advances in Cryptology - ASIACRYPT 2016","volume":"10031","author":"I.\u00a0Chillotti","year":"2016"},{"key":"ref13:AC:CKKS17","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"409","DOI":"10.1007\/978-3-319-70694-8_15","article-title":"Homomorphic Encryption for Arithmetic of Approximate\n  Numbers","volume-title":"Advances in Cryptology - ASIACRYPT 2017","volume":"10624","author":"J.\u00a0H.\u00a0Cheon","year":"2017"},{"key":"ref14:helib","article-title":"HElib","year":"2019"},{"key":"ref15:sealcrypto","article-title":"Microsoft SEAL (release 4.0)","year":"2022"},{"key":"ref16:EC:LPR13","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1007\/978-3-642-38348-9_3","article-title":"A Toolkit for Ring-LWE Cryptography","volume-title":"Advances in Cryptology - EUROCRYPT 2013","volume":"7881","author":"V.\u00a0Lyubashevsky","year":"2013"},{"key":"ref17:EC:GenHalSma12","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-29011-4_28","article-title":"Fully Homomorphic Encryption with Polylog Overhead","volume-title":"Advances in Cryptology - EUROCRYPT 2012 - 31st Annual\n  International Conference on the Theory and Applications of Cryptographic\n  Techniques, Cambridge, UK, April 15-19, 2012. Proceedings","volume":"7237","author":"Craig Gentry","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642290107"},{"key":"ref18:C:GenHalSma12","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"850","DOI":"10.1007\/978-3-642-32009-5_49","article-title":"Homomorphic Evaluation of the AES Circuit","volume-title":"Advances in Cryptology - CRYPTO 2012 - 32nd Annual\n  Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012.\n  Proceedings","volume":"7417","author":"Craig Gentry","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642320088"},{"key":"ref19:JoC:CGGI20","doi-asserted-by":"crossref","first-page":"34","DOI":"10.1007\/s00145-019-09319-x","article-title":"TFHE: Fast Fully Homomorphic Encryption Over the Torus","volume":"33","author":"Ilaria Chillotti","year":"2020","journal-title":"J. Cryptology"},{"key":"ref20:CKKS-RH","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-031-53368-6_16","article-title":"On the Precision Loss in Approximate Homomorphic\n  Encryption","volume-title":"Selected Areas in Cryptography - SAC 2023 - 30th\n  International Conference, Fredericton, Canada, August 14-18, 2023, Revised\n  Selected Papers","volume":"14201","author":"Anamaria Costache","year":"2023"},{"key":"ref21:li-etal-crypto22","first-page":"560","article-title":"Securing Approximate Homomorphic Encryption using\n  Differential Privacy","volume-title":"Advances in Cryptology - CRYPTO 2022","volume":"LNCS 13507","author":"B.\u00a0Li","year":"2022"},{"key":"ref22:OpenFHE","series-title":"WAHC'22","doi-asserted-by":"publisher","first-page":"53","DOI":"10.1145\/3560827.3563379","article-title":"OpenFHE: Open-Source Fully Homomorphic Encryption Library","volume-title":"Proceedings of the 10th Workshop on Encrypted Computing &\n  Applied Homomorphic Cryptography","author":"Ahmad Al Badawi","year":"2022"},{"key":"ref23:ESORICS:CosLaiPla20","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1007\/978-3-030-59013-0_27","article-title":"Evaluating the Effectiveness of Heuristic Worst-Case Noise\n  Analysis in FHE","volume-title":"Computer Security - ESORICS 2020 - 25th European Symposium\n  on Research in Computer Security, ESORICS 2020, Guildford, UK, September\n  14-18, 2020, Proceedings, Part II","volume":"12309","author":"Anamaria Costache","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030590123"},{"key":"ref24:GNSJ24","article-title":"Key Recovery Attacks on Approximate Homomorphic Encryption\n  with Non-Worst-Case Noise Flooding Countermeasures","volume-title":"33rd USENIX Security Symposium (USENIX Security 24).\n  Philadelphia, PA: USENIX Association","author":"Qian Guo","year":"2024"},{"key":"ref25:RSA:CNP23","series-title":"Lecture Notes in Computer Science","first-page":"29","article-title":"Optimisations and Tradeoffs for HElib","volume-title":"Topics in Cryptology - CT-RSA 2023 - Cryptographers' Track\n  at the RSA Conference 2023, San Francisco, CA, USA, April 24-27, 2023,\n  Proceedings","volume":"13871","author":"Anamaria Costache","year":"2023"},{"key":"ref26:RSA:CosSma16","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","first-page":"325","DOI":"10.1007\/978-3-319-29485-8_19","article-title":"Which Ring Based Somewhat Homomorphic Encryption Scheme is\n  Best?","volume-title":"Topics in Cryptology - CT-RSA 2016 - The Cryptographers'\n  Track at the RSA Conference 2016, San Francisco, CA, USA, February 29 -\n  March 4, 2016, Proceedings","volume":"9610","author":"Ana Costache","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319294841"},{"key":"ref27:PhD:Iliashenko19","article-title":"Optimisations of fully homomorphic encryption","author":"I. Iliashenko","year":"2019"},{"key":"ref28:HS20","article-title":"Design and implementation of HElib: a homomorphic\n  encryption library","author":"Shai Halevi","year":"2020"},{"key":"ref29:RSA:KPP22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-030-95312-6_6","article-title":"Approximate Homomorphic Encryption with Reduced\n  Approximation Error","volume-title":"Topics in Cryptology - CT-RSA 2022 - Cryptographers' Track\n  at the RSA Conference 2022, Virtual Event, March 1-2, 2022, Proceedings","volume":"13161","author":"Andrey Kim","year":"2022"},{"key":"ref30:AC:KPZ21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-030-92078-4_21","article-title":"Revisiting Homomorphic Encryption Schemes for Finite\n  Fields","volume-title":"Advances in Cryptology - ASIACRYPT 2021 - 27th\n  International Conference on the Theory and Application of Cryptology and\n  Information Security, Singapore, December 6-10, 2021, Proceedings, Part\n  III","volume":"13092","author":"Andrey Kim","year":"2021"},{"key":"ref31:MathCrypt:MP19","doi-asserted-by":"crossref","first-page":"45","DOI":"10.1515\/jmc-2020-0073","article-title":"Discretisation and Product Distributions in Ring-LWE","volume":"15","author":"Sean Murphy","year":"2020","journal-title":"Journal of Mathematical Cryptology"},{"key":"ref32:BMCM23","first-page":"600","article-title":"Improving and Automating BFV Parameters Selection: An\n  Average-Case Approach","author":"Beatrice Biasioli","year":"2023","journal-title":"IACR Cryptol. ePrint Arch."},{"key":"ref33:BiaMar23","author":"Beatrice Biasioli","year":"2023"},{"key":"ref34:EC:MicPei12","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"700","DOI":"10.1007\/978-3-642-29011-4_41","article-title":"Trapdoors for Lattices: Simpler, Tighter, Faster,\n  Smaller","volume-title":"Eurocrypt 2012","volume":"7237","author":"D.\u00a0Micciancio","year":"2012"},{"key":"ref35:ACISP:MP19","series-title":"LNCS","first-page":"251","article-title":"$\\delta$-subgaussian Random Variables in Cryptography","volume-title":"ACISP 2019: The 24th Australasian Conference on Information\n  Security and Privacy","volume":"11547","author":"S.\u00a0Murphy","year":"2019"},{"key":"ref36:stroock-book","article-title":"Probability Theory: An Analytic View","author":"D.\u00a0Stroock","year":"2011"},{"key":"ref37:tao-vu-acta-2011","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s11511-011-0061-3","article-title":"Random matrices: Universality of local eigenvalue\n  statistics","volume":"206","author":"T.\u00a0Tao","year":"2011","journal-title":"Acta Mathematica"},{"key":"ref38:billingsley-book","article-title":"Probability and Measure","author":"P.\u00a0Billingsley","year":"1995"},{"key":"ref39:CSBB24","article-title":"On the practical CPAD security of \u201cexact\u201d and\n  threshold FHE schemes and libraries","author":"Marina Checri","year":"2024"},{"key":"ref40:CCPSS24","article-title":"Attacks Against the INDCPA-D Security of Exact FHE\n  Schemes","author":"Jung Hee Cheon","year":"2024"},{"key":"ref41:ABMP24","article-title":"Application-Aware Approximate Homomorphic Encryption:\n  Configuring FHE for Practical Use","author":"Andreea Alexandru","year":"2024"},{"key":"ref42:HESS","article-title":"Homomorphic Encryption Security Standard","author":"M. Albrecht","year":"2018"},{"key":"ref43:grimmett-stirzaker-book","article-title":"Probability And Random Processes","author":"G.\u00a0Grimmett","year":"2001"},{"key":"ref44:PhD:Player18","article-title":"Parameter selection in lattice-based cryptography","author":"Rachel Player","year":"2018"},{"key":"ref45:DBLP:conf\/eurocrypt\/2012","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-29011-4","article-title":"Advances in Cryptology - EUROCRYPT 2012 - 31st Annual\n  International Conference on the Theory and Applications of Cryptographic\n  Techniques, Cambridge, UK, April 15-19, 2012. Proceedings","volume":"7237","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642290107"},{"key":"ref46:DBLP:conf\/crypto\/2012","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32009-5","article-title":"Advances in Cryptology - CRYPTO 2012 - 32nd Annual\n  Cryptology Conference, Santa Barbara, CA, USA, August 19-23, 2012.\n  Proceedings","volume":"7417","year":"2012","ISBN":"https:\/\/id.crossref.org\/isbn\/9783642320088"},{"key":"ref47:DBLP:conf\/ctrsa\/2016","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-29485-8","article-title":"Topics in Cryptology - CT-RSA 2016 - The Cryptographers'\n  Track at the RSA Conference 2016, San Francisco, CA, USA, February 29 -\n  March 4, 2016, Proceedings","volume":"9610","year":"2016","ISBN":"https:\/\/id.crossref.org\/isbn\/9783319294841"},{"key":"ref48:DBLP:conf\/esorics\/2020-2","series-title":"Lecture Notes in Computer Science","isbn-type":"print","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59013-0","article-title":"Computer Security - ESORICS 2020 - 25th European Symposium\n  on Research in Computer Security, ESORICS 2020, Guildford, UK, September\n  14-18, 2020, Proceedings, Part II","volume":"12309","year":"2020","ISBN":"https:\/\/id.crossref.org\/isbn\/9783030590123"}],"container-title":["IACR Communications in Cryptology"],"original-title":[],"language":"en","deposited":{"date-parts":[[2024,12,10]],"date-time":"2024-12-10T21:26:53Z","timestamp":1733866013000},"score":1,"resource":{"primary":{"URL":"https:\/\/cic.iacr.org\/p\/1\/2\/7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,8]]},"references-count":48,"URL":"https:\/\/doi.org\/10.62056\/ay76c0kr","archive":["Internet Archive","Internet Archive"],"relation":{},"ISSN":["3006-5496"],"issn-type":[{"value":"3006-5496","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,8]]},"assertion":[{"value":"2024-03-20","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-06-03","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"cc1-2-6"}}